AC on #1#2#3 评测记录

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
vector<pair<int,int> > e[N];
int n,m;
int f[N],d[N],arc[20][N],st[20][N];
bool vis[N];
priority_queue<pair<int,pair<int,int> > > q;
int findn(int t){
	return f[t] == t?t:f[t] = findn(f[t]);
}
void add(int u,int v,int w){
	e[u].push_back(make_pair(v,w));
	e[v].push_back(make_pair(u,w));
}
void kru(){
	for(int i=1;i<=n;i++){
		f[i] = i;
	}
	int cnt = 1;
	while(cnt < n && !q.empty()){
		int x = q.top().second.first;
		int y = q.top().second.second;
		int w = q.top().first;
		
		int xx = findn(x);
		int yy = findn(y);
		
		q.pop();
		if(xx != yy){
			f[xx] = yy;
			cnt ++;
			add(x,y,w);
//			printf("%d %d %d\n",x,y,w);
		}
	}
}
void dfs(int now,int fa){
	d[now] = d[fa] + 1;
	arc[0][now] = fa;
	for(int i=0;i<e[now].size();i++){
		int v = e[now][i].first;
		if(v == fa){
			continue;
		}
		st[0][v] = e[now][i].second;
		dfs(v,now);
	} 
}
int query(int x,int y){
	int ans = 0x3f3f3f3f;
	if(d[x] < d[y]){
		swap(x,y);
	}//保证d[x] >= d[y];
	for(int i=18;i>=0;i--){
		if(d[arc[i][x]] >= d[y]){
			ans = min(ans,st[i][x]);
			x = arc[i][x];	
		}
	}
	if(x == y){
		return ans;
	}
	for(int i=18;i>=1;i--){
		if(arc[i][x] != arc[i][y]){
			ans = min(ans,st[i][x]);
			ans = min(ans,st[i][y]);
			x = arc[i][x];
			y = arc[i][y];
		}
	}
	ans = min(ans,st[0][x]);
	ans = min(ans,st[0][y]);
	return ans;
	return arc[0][x];
}
void init(){
	for(int i=1;i<=18;i++){
		for(int j=1;j<=n;j++){
			arc[i][j] = arc[i-1][arc[i-1][j]];
			st[i][j] = min(st[i-1][j],st[i-1][arc[i-1][j]]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		q.push(make_pair(w,make_pair(v,u)));
	}
	int que;
	scanf("%d",&que);
	kru();
	for(int i=1;i<=n;i++){
		int xx = findn(i);
		if(vis[xx] == false){
			dfs(i,0);
			vis[xx] = true;
		}
	}
	
	init();
	for(int i=1;i<=que;i++){
		int x,y,lca;
		scanf("%d%d",&x,&y);
		if(findn(x) != findn(y)){
			puts("-1");
		}else{
			printf("%d\n",query(x,y));
		}
	}
}