记录编号	174813	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2015-08-03 06:06:10	内存使用	5.58 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN 999999999
int tot,n,m,q,head[10003],father[10005],fa[10005][30];
int deep[10005],f[10005][30],ans,x,y;
inline int in()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return x;
}
struct dr{
	int kaishi;
	int zhong;
	int juli;
	bool operator<(const dr &a)const{
		return juli>a.juli;}
}edge[150005];
void  SWAP(int &x,int &y){
	x^=y;
	y^=x;
	x^=y;
}
struct dd{
	int zhong;
	int next;
	int juli;
}jie[100010];
int find(int x){
	if(father[x]==x) return x;
	father[x]=find(father[x]);
	return father[x];
}
void jia(int x,int y,int z){
	tot++;
	jie[tot].zhong=y;
	jie[tot].juli=z;
	jie[tot].next=head[x];
	head[x]=tot;
}
void Kur(){
	for(int i=1;i<=m;++i){
		int x=edge[i].kaishi;
		int y=edge[i].zhong;
		if(find(x)!=find(y)){
			//father[x]=y;
			father[find(y)]=find(x);
			jia(x,y,edge[i].juli);
			jia(y,x,edge[i].juli);
		}
	}
}
void dfs(int x,int y){
	for(int i=head[x];i;i=jie[i].next){
		int yu=jie[i].zhong;
		if(!deep[yu]){
			deep[yu]=deep[x]+1;
			fa[yu][0]=x;
			f[yu][0]=jie[i].juli;
			dfs(yu,y+1);
		}
	}
}
void dp(){
	for(int i=1;i<=n;++i){
		if(!deep[i]){
			deep[i]=1;
			dfs(i,1);
		}
	}
}
int LCA(int x,int y){
    if(deep[x]<deep[y]) SWAP(x,y);
	int i;
	for(i=0;(1<<i)<=deep[x];i++);
	i--;
	for(int j=i;j>=0;j--)
	 if(deep[x]-(1<<j)>=deep[y]){
	 	ans=min(ans,f[x][j]);
	 	x=fa[x][j];
	 }
	if(x==y) return ans;
	for(int j=i;j>=0;j--){
		if(fa[x][j]&&fa[x][j]!=fa[y][j]){
			{
				ans=min(min(f[x][j],f[y][j]),ans);
				x=fa[x][j];
				y=fa[y][j];
			}
		}
	}
	ans=min(ans,min(f[y][0],f[x][0]));
	return ans;
}
int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	n=in();
	m=in();
	for(int i=1;i<=n;++i)
	 father[i]=i;
	for(int i=1;i<=m;++i){
	     edge[i].kaishi=in();
		 edge[i].zhong=in();
		 edge[i].juli=in();
	}
	sort(edge+1,edge+m+1);
	Kur();
	dp();
	for(int j=1;(1<<j)<=n;++j)
	 for(int i=1;i<=n;++i)
	   {
	 	  fa[i][j]=fa[fa[i][j-1]][j-1];
	 	  f[i][j]=min(f[i][j-1],f[fa[i][j-1]][j-1]);
	   }
	q=in();
	for(int i=1;i<=q;++i){
		x=in(),y=in();
		if(find(x)!=find(y))
		  printf("%d\n",-1);
		else
		{   ans=0x7fffffff;
		    
			printf("%d\n",LCA(x,y));
		}
	}
}