记录编号	432169	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	>.<	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2017-08-02 22:43:11	内存使用	2.60 MiB

#include <bits/stdc++.h>

#define N 100010
#define INF 0x3f3f3f3f

using namespace std;

struct node
{
	int x,y,v;
}b[N];

int n,m,maxd[N],fa[N],val[N];

bool cmp(node a,node b)
{
	return a.v > b.v;
}

int getf(int x,int &dep)
{
	dep = 0;
	while(x!=fa[x]) x=fa[x], dep++;
	return x;
}

int main()
{
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].v);
	sort(b+1,b+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i] = i, val[i] = INF, maxd[i]=1;
	for(int i=1,tp;i<=m;i++)
	{
		int r1 = getf(b[i].x,tp);
		int r2 = getf(b[i].y,tp);
		if(r1==r2) continue;
		if(maxd[r1]>maxd[r2]) swap(r1,r2);
		fa[r1] = r2;
		val[r1] = b[i].v;
		maxd[r2] = max(maxd[r2], maxd[r1]+1);
	}
	int q,x,y,d1,d2;
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&x,&y);
		int r1 = getf(x,d1);
		int r2 = getf(y,d2);
		if(r1!=r2) puts("-1");
		else
		{
			int ans=INF;
			if(d1<d2) swap(x,y), swap(d1,d2);
			for(int i=1;i<=d1-d2;i++)
			{
				ans = min(ans,val[x]);
				x=fa[x];
			}
			while(x!=y)
			{
				ans = min(ans, min(val[x],val[y]));
				x=fa[x],y=fa[y];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}