记录编号	600827	评测结果	AAAAAAAAAAAAMMMMMMMM
题目名称	1439.[NOIP 2013]货车运输	最终得分	60
用户昵称	徐诗畅	是否通过	未通过
代码语言	C++	运行时间	2.208 s
提交时间	2025-05-19 16:41:13	内存使用	55.30 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,q,fa[N],cnt; 
struct edge{
	int a,b,z;
	bool operator<(const edge r)const{return z<r.z;}
};
struct quest{
	int a,b,ans;
    bool vis;
}que[N];
priority_queue<edge>p;
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
	    int x,y,z; scanf("%d%d%d",&x,&y,&z);
        p.push(edge{x,y,z});
    }
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
        scanf("%d%d",&que[i].a,&que[i].b);
        que[i].vis=0; que[i].ans=-1;
    }
	while(!p.empty()&&cnt<n){
		edge x=p.top();
		p.pop();
		x.a=find(x.a); x.b=find(x.b);
		if(x.a!=x.b){
			cnt++;
			fa[x.a]=x.b;
			for(int i=1;i<=q;i++){
				if(!que[i].vis){
					que[i].a=find(que[i].a);
					que[i].b=find(que[i].b);
					if(que[i].a==que[i].b){
						que[i].ans=x.z;
						que[i].vis=1;
					}
				}
			}
		}
	}
	for(int i=1;i<=q;i++) printf("%d\n",que[i].ans);
	return 0;
}