求助 dalao

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace  std;
#define int long long
#define interesting int
const int maxm=6e5+3;
const int maxn=4e5+3;
int n,m,k,Q;
namespace union_set{
	int fa[maxn];
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	void add(int x,int y,int &cnt){
		fa[x]=fa[y]=++cnt;
	}
	bool query(int x,int y){
		return find(x)==find(y);
	}
	void init(int n){
		for(int i=1;i<=n;i++){
			fa[i]=i; 
		} 
	}
}
struct edge1{
	int u,v,w;
	edge1(int u=0,int v=0,int w=0): u(u),v(v),w(w){}
	bool operator<(const edge1 o)const{return w<o.w;}
}e2[maxm<<2];
namespace adjacency_krusakl{
	
	void addedge(int i,int x,int y,int w){
		e2[i]=edge1(x,y,w);
	}
	void Sort(int m){
		sort(e2+1,e2+m+1);
	}
}
namespace adjacency_dijkstra_UVW{
	struct edge{
		int v,w;
		edge(int v=0,int w=1): v(v),w(w){}
	};
	vector<edge>e[maxm];
	void add_edge(int u,edge v,bool type){
		e[u].push_back(v);
		if(type){//无向图 
			e[v.v].push_back(edge(u,v.w));
		}
	}
}
vector<int>e1[maxm<<1];
namespace adjacency_dijkstra_UV{
	void add_edge(int u,int v,bool type){
		e1[u].push_back(v);
		if(type){//无向图 
			e1[v].push_back(u);
		}
	}
}
int dis[maxn];
namespace dijkstra{
	using namespace adjacency_dijkstra_UVW;
	struct di{
		int id,dis;
		di(int id=0,int dis=0): id(id),dis(dis){}
		bool operator<(const di o)const{return dis>o.dis;}
	};
	priority_queue<di>q;
	void dijkstra(int kk){
		memset(dis,0x3f,sizeof dis);
		for(int i=1;i<=kk;i++){
			q.push(di(i,dis[i]=0));
		}
		while(!q.empty()){
			di az=q.top();
			q.pop();
			int u=az.id;
			if(az.dis==dis[u]){
				for(auto v:e[u]){
					if(dis[v.v]>dis[u]+v.w){
						q.push(di(v.v,dis[v.v]=dis[u]+v.w));
					}
				}
			}
		}
	}	
}
interesting ans[maxn];
namespace krusakl{
	using namespace adjacency_krusakl;
	using namespace union_set;
	int krusakl(){
		Sort(m);
		init(n<<1);
		long long cnt=n;
		for(int i=1;i<=m;i++){
			int x=find(e2[i].u),y=find(e2[i].v),w=e2[i].w;
			if(x!=y){
				add(x,y,cnt);
				ans[cnt]=w;
				adjacency_dijkstra_UV::add_edge(cnt,x,0);
				adjacency_dijkstra_UV::add_edge(cnt,y,0);
			}
		}
		return cnt;
	}
}
int Fa[maxn][22],f[maxn];
namespace LCA{
	using namespace adjacency_dijkstra_UV;
	void dfs(int u,int fa){
		f[u]=f[fa]+1;
		Fa[u][0]=fa;
		for(int i=1;(1<<i)<=f[u];i++){
			Fa[u][i]=Fa[Fa[u][i-1]][i-1];
		}
		for(auto v:e1[u]){
			if(v==fa)continue;
			dfs(v,u);
		}
	}
	int lca(int u,int v){
		if(f[u]<f[v]){
			swap(u,v);
		}
		for(int t=0,cnt=f[u]-f[v];cnt;t++,cnt>>=1){
			if(cnt&1)u=Fa[u][t];
		}
		if(u==v)return u;
		for(int t=17;~t;t--){
			if(Fa[u][t]!=Fa[v][t]){
				u=Fa[u][t];
				v=Fa[v][t];
			}
		}
		return Fa[u][0];
	}
}
using namespace krusakl;
using namespace dijkstra;
using namespace LCA;
using namespace union_set; 
signed main(){
	cin>>n>>m>>k>>Q;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		adjacency_krusakl::addedge(i,x,y,z);
		adjacency_dijkstra_UVW::add_edge(x,adjacency_dijkstra_UVW::edge(y,z),1);
	}
	dijkstra::dijkstra(k);
	for(int i=1;i<=m;i++){
		e2[i].w+=dis[e2[i].u]+dis[e2[i].v];
	}
	int x=krusakl::krusakl();
	dfs(x,0);
	while(Q--){
		int u,v;
		cin>>u>>v;
		cout<<ans[lca(u,v)]<<endl;
	}
	return 0;
}

部分参照第2篇题解。