萌新求助 样例 RE
查看原帖
萌新求助 样例 RE
310818
蒟酱厂妹楼主2023/3/25 10:32

如题,在运行到第 101 行时程序突然崩溃,但是并没有产生数据越界的情况,怎么回事呢

//不向焦虑与抑郁投降,这个世界终会有我们存在的地方。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<tuple>
#include<ctime>
#include<random>
#include<queue>
#if __cplusplus>=202002L
#include<ranges>
namespace vw=std::views;
#endif
struct _time{~_time(){std::cerr<<"\n\033[33;40m"<<1.*clock()/CLOCKS_PER_SEC<<"s\033[37;40m";}}_TM;
#define siz(x) int((x).size())
#define cauto const auto
#define all(x) std::begin(x),std::end(x)
#define rall(x) std::rbegin(x),std::rend(x)
#define sqrt __builtin_sqrt
#define fi first
#define se second
#define continue(x...) {x;continue;}
#define break(x...) {x;break;}
using std::cin;using std::cout;
using std::max;using std::min;
using std::tie;using std::ignore;
template<typename any>constexpr any&cmin(any&x,any&&y){if(y<x)x=y;return x;}
template<typename any>constexpr any&cmax(any&x,any&&y){if(x<y)x=y;return x;}
template<typename any,typename...args>constexpr any&cmin(any&x,any&&y,args&&...z){if(y<x)x=y;return cmin(x,std::forward<any>(z)...);}
template<typename any,typename...args>constexpr any&cmax(any&x,any&&y,args&&...z){if(x<y)x=y;return cmax(x,std::forward<any>(z)...);}
using loli=long long;
using unt=unsigned;
using lolu=unsigned long long;
using lodb=long double;
using venti=__int128_t;
using pii=std::pair<int,int>;
using pli=std::pair<loli,int>;
using tiii=std::tuple<int,int,int>;
using inlsi=const std::initializer_list<int>&;
using bsi=std::basic_string<int>;
using bsl=std::basic_string<loli>;
using bsc=std::string;
using std::operator""s;
#if __cplusplus>=201703L
using bscv=std::string_view;
using std::operator""sv;
#endif
std::mt19937 rng(std::random_device{}());
#define type std::pair<T1,T2>
template<typename T1,typename T2>std::istream&operator>>(std::istream&x,type&y){return x>>y.fi>>y.se;}
template<typename T1,typename T2>std::ostream&operator<<(std::ostream&x,const type&y){return x<<y.fi<<' '<<y.se;}
template<typename T1,typename T2>type operator+(const type&x,const type&y){return{x.fi+y.fi,x.se+y.se};}
template<typename T1,typename T2>type operator+=(type&x,const type&y){x.fi+=y.fi;x.se+=y.se;return x;}
template<typename T1,typename T2>type operator-(const type&x,const type&y){return{x.fi-y.fi,x.se-y.se};}
template<typename T1,typename T2>type operator-=(type&x,const type&y){x.fi-=y.fi;x.se-=y.se;return x;}
#undef type
template<typename any>any get(std::istream&x=cin){any y;x>>y;return y;}
template<typename any>any&STLcls(any &x){any{}.swap(x);return x;}
constexpr venti operator""_vt(lolu x){return venti(x);}
constexpr bool ying=false,yang=true;
constexpr int N=1e5+1,M=45;
int n,m,Q;
bool vis[N];
std::vector<std::pair<int,std::vector<loli>>>d;
std::vector<pii>g1[N],g2[N];
std::vector<tiii>e;
std::priority_queue<pli,std::vector<pli>,std::greater<>>q;
struct bcj{
	std::vector<int>fa;
	bcj():fa(n+1){for(int i=1;i<=n;i++)fa[i]=i;}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	bool check(int x,int y){return find(x)!=find(y);}
	void merge(int x,int y){if((x=find(x))!=(y=find(y)))fa[x]=y;}
};
struct sp{
	std::vector<int>fa,dep,gs,top,sz;
	std::vector<loli>dis;
	// sp():fa(n+1),dep(n+1),gs(n+1),top(n+1),sz(n+1){sz[1]=dep[1]=1;dfs1(1);dfs2(1,1);}
	sp():fa(n+1),dep(n+1),gs(n+1),top(n+1),sz(n+1){
		std::cerr<<siz(sz)<<'\n';
		std::cerr<<"tree:\n";
		for(int i=1;i<=n;i++)
			for(auto[v,w]:g2[i])
				std::cerr<<i<<' '<<v<<' '<<w<<'\n';

		sz[1]=dep[1]=1;
		std::cerr<<"dfs1\n";
		dfs1(1);
		std::cerr<<"dfs2\n";
		dfs2(1,1);
		}
	void dfs1(int u){
		for(auto[v,w]:g2[u]){
			std::cerr<<u<<' '<<v<<' '<<w<<'\n';
			if(v==fa[u])continue;
			std::cerr<<u<<' '<<v<<' '<<w<<'\n';
			fa[v]=u;std::cerr<<"q\n";
			dep[v]=dep[u]+1;std::cerr<<"q\n";
			sz[v]=1;std::cerr<<"q\n";
			dis[v]=dis[u]+w;std::cerr<<"q\n";// boom
			std::cerr<<u<<' '<<v<<' '<<w<<'\n';
			dfs1(v);sz[u]+=sz[v];
			if(sz[v]>sz[gs[u]])gs[u]=v;
		}
	}
	void dfs2(int u,int t){
		top[u]=t;if(!gs[u])return;else dfs2(gs[u],t);
		for(auto[v,w]:g2[u])if(v!=fa[u]&&v!=gs[u])dfs2(v,v);
	}
	int LCA(int x,int y){
		for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])std::swap(x,y);
		return dep[x]<dep[y]?x:y;
	}
	loli path(int u,int v){return dis[u]+dis[v]-2*dis[LCA(u,v)];}
};
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>m;e.reserve(m);
	bcj dsu;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		g1[u].emplace_back(v,w);
		g1[v].emplace_back(u,w);
		e.emplace_back(w,u,v);
	}
	sort(all(e));
	for(auto[w,u,v]:e)
		if(dsu.check(u,v)){
			g2[u].emplace_back(v,w);
			g2[v].emplace_back(u,w);
			dsu.merge(u,v);
		}else d.emplace_back(u,n+1),d.emplace_back(v,n+1);
		std::cerr<<"QwQ\n";
	sp tr;
		std::cerr<<"QwQ\n";
	for(auto&[bg,dis]:d){
		memset(&dis[0]+1,0x3f,sizeof(loli)*n);
		memset(vis+1,0,sizeof(bool)*n);
		dis[bg]=0;q.emplace(0ll,bg);
		while(!q.empty()){
			int u=q.top().se;q.pop();
			if(vis[u])continue;else vis[u]=true;
			for(auto[v,w]:g1[u])
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if(!vis[v])q.emplace(dis[v],v);
				}
		}
	}
	cin>>Q;for(int u,v;Q--;){
		cin>>u>>v;
		loli res=tr.path(u,v);
		for(auto&[bg,dis]:d)
			cmin(res,dis[u]+dis[v]);
		cout<<res<<'\n';
	}
	return 0;
}
2023/3/25 10:32
加载中...