WA3

通读了半个小时也没有发现问题/ll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
const int mxn=5e5+5;
ll dist[44][mxn];int imp[44],cc;
vector<pair<int,ll> >g[mxn],tg[mxn];//g是图边 tg是树边
int n,m;
int fa[mxn];
inline void init(){for(int i=1;i<=n;++i)fa[i]=i;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void bfs(int id){
	int bg=imp[id];
	priority_queue<pair<ll,int> >q;for(;q.size();)q.pop();
	q.push(mp(0,bg));
	dist[id][bg]=0;
	for(;q.size();){
		pair<ll,int>p=q.top();q.pop();
		int x=p.second;
		ll cur=-p.first;
		if(dist[id][x]<cur)continue;
		for(pair<int,ll> ee:g[x]){
			int y=ee.first;ll w=ee.second;
			if(dist[id][y]>cur+w){
				dist[id][y]=cur+w;
				q.push(mp(-dist[id][y],y));
			}
		}
	}
}
int dep[mxn],par[mxn][22];
ll sum[mxn];
inline void dfs(int x,int pa=1,int deep=1,ll sm=0){
	dep[x]=deep,par[x][0]=pa,sum[x]=sm;
	for(pair<int,ll> ee:tg[x]){
		int y=ee.first;ll w=ee.second;
		if(y!=pa)dfs(y,x,deep+1,sm+w);
	}
}
inline void prep(){for(int j=1;j<20;++j)for(int i=1;i<=n;++i)par[i][j]=par[par[i][j-1]][j-1];}
inline int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int i=19;~i;--i)if(dep[par[y][i]]>=dep[x])y=par[y][i];
	for(int i=19;~i;--i)if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i];
	for(;x!=y;)x=par[x][0],y=par[y][0];
	return x;
}
inline ll dis(int x,int y){
	int LCA=lca(x,y);
	return sum[x]+sum[y]-2*sum[LCA];
}
int added[mxn];
inline void solve(){
	cin>>n>>m;init();
	for(int i=1;i<=m;++i){
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back(mp(v,w)),g[v].push_back(mp(u,w));
		if(find(u)==find(v)){
			if(!added[u])imp[++cc]=u;
			if(!added[v])imp[++cc]=v;
			added[u]=1;
			added[v]=1;
		}else fa[find(u)]=find(v),tg[u].push_back(mp(v,w)),tg[v].push_back(mp(u,w));
	}
//	for(int i=1;i<=cc;++i){
//		cerr<<imp[i]<<" : ";
//		for(int j=1;j<=n;++j)cerr<<dist[i][j]<<' ';cerr<<'\n';
//	}
	memset(dist,63,sizeof(dist));
	for(int i=1;i<=cc;++i)bfs(i);
	dfs(1);
	int q;cin>>q;
	for(;q--;){
		int u,v;cin>>u>>v;
		ll ans=dis(u,v);
//		cerr<<"?? "<<dis(u,v)<<'\n';
		for(int i=1;i<=cc;++i)ans=min(ans,dist[i][u]+dist[i][v]);
		cout<<ans<<'\n';
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	//cin>>T;
	for(;T--;)solve();
	return 0;
}