记录编号	121999	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.476 s
提交时间	2014-09-22 12:09:07	内存使用	2.75 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<climits>
#include<cmath>
#define Maxn 10001
#define Maxp 30001
#define Maxm 50001
using namespace std;
struct node{
	int x,y,v;
	bool operator<(const node &a)const{
		return v>a.v;
	}
}V[Maxm]={0},A[Maxp]={0};
vector<int> T[Maxn],C[Maxn];
int n,m,p,father[Maxn],L[Maxn]={0},kt;
int fa[Maxn][20]={0},w[Maxn][20]={0};
int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}
void unionn(int x,int y){
	int a=find(x);
	int b=find(y);
	if(a!=b) father[b]=a;
}
void dfs(int now,int deep){
	L[now]=deep;
	for(int j=0;j<T[now].size();j++)
	{
		if(!fa[T[now][j]][0])
		{
			fa[T[now][j]][0]=now;
			w[T[now][j]][0]=C[now][j];
			dfs(T[now][j],deep+1);
		}
	}
}
int LCA(int x,int y){
	int res=INT_MAX;
	if(L[x]<L[y]) swap(x,y);
	for(int i=kt-1;i>=0;i--)
	{
		if(L[fa[x][i]]>=L[y])
		{
			res=min(res,w[x][i]);
			x=fa[x][i];
		}
	}
	if(x!=y)
	{
		for(int j=kt-1;j>=0;j--)
		{
			if(fa[x][j]!=fa[y][j])
			{
				res=min(res,min(w[x][j],w[y][j]));
				x=fa[x][j];
				y=fa[y][j];
			}
		}
		res=min(res,min(w[x][0],w[y][0]));
		x=fa[x][0];
		y=fa[y][0];
	}
	return res;
}
void work(){
	int team=p;
	for(int i=1;i<=n;i++) father[i]=i;
	sort(V+1,V+m+1);
	for(int i=1;team&&i<=m;i++)
	{
		if(find(V[i].x)!=find(V[i].y))
		{
			unionn(V[i].x,V[i].y);
			T[V[i].x].push_back(V[i].y);
			C[V[i].x].push_back(V[i].v);
			T[V[i].y].push_back(V[i].x);
			C[V[i].y].push_back(V[i].v);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!fa[i][0])
		{
			w[i][0]=INT_MAX;
			fa[i][0]=i;
			dfs(i,1);
		}
	}
	for(int i=1;i<kt;i++)
	{
		for(int j=1;j<=n;j++)
		{
			fa[j][i]=fa[fa[j][i-1]][i-1];
			w[j][i]=min(w[j][i-1],w[fa[j][i-1]][i-1]);
		}
	}
	for(int i=1;i<=p;i++)
	{
		int tmp=LCA(A[i].x,A[i].y);
		if(tmp==INT_MAX)
			cout<<-1<<endl;
		else cout<<tmp<<endl;
	}
}
void init(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>V[i].x>>V[i].y>>V[i].v;
	cin>>p;
	for(int i=1;i<=p;i++)
		cin>>A[i].x>>A[i].y;
	kt=(int)(log((double)n)/log(2.0))+1;
}
int main(){
	init();
	work();
	return 0;
}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/