记录编号	312943	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	0.361 s
提交时间	2016-09-27 20:58:43	内存使用	22.63 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=50000+10;
struct edges
{
  int fr;int to; int w;int id;
  bool operator <(const edges x) const { return w>x.w;}
}  edge[maxn*3];
vector <int> G[maxn];  int deep=1; int d[maxn]; int w[maxn][50];
int n,m;int tot=0;int fa[maxn];int maxi;
int gef(int x)  { return fa[x]==x?x:fa[x]=gef(fa[x]);}
int f[maxn][50];
void krus()
{  for(int i=1;i<=n;i++) fa[i]=i;
  // for(int i=1;i<=n;i++) printf("f[%d]=%d\n",i,gef(i));
   sort(edge+1,edge+m+1);
   for(int i=1;i<=m;i++)
    {  
	 
	   int a=edge[i].fr; int b=edge[i].to;
	    // printf("%d %d %d\n",a,b,edge[i].w);
	   if(gef(a)!=gef(b))
	   {
	      G[a].push_back(i);
	      //printf("from:%d to:%d dist:%d id:%d\n",edge[i].fr,edge[i].to,edge[i].w,edge[i].id);
		  G[b].push_back(edge[i].id);
		  fa[gef(a)]=gef(b);
		  //printf("faa%d fab%d\n",gef(a),gef(b));
		 
	   }
//	   for(int i=1;i<=n;i++) printf("%d ",fa[i]);
	   
	    // for(int i=1;i<=n;i++) printf("f[%d]=%d\n",i,gef(i));
	}
	//for(int i=1;i<=m*2+10;i++,putchar('\n')) printf("from%d to%d dist%d",edge[i].fr,edge[i].to,edge[i].w);
	return;
}
void init()
{   
     scanf("%d%d",&n,&m);
     memset(f,0,sizeof(f));
	 for(int i=1;i<=m;i++)
	 {
	   tot++;
	   scanf("%d%d%d",&edge[tot].fr,&edge[tot].to,&edge[tot].w);
	   edge[tot+m+5].fr=edge[tot].to;
	   edge[tot+m+5].to=edge[tot].fr;
	   edge[tot+m+5].w=edge[tot].w;
	   edge[tot].id=tot+m+5;
	   /*G[fr].push_back(tot);
	   G[to].push_back(tot+m+1);*/
	  }
//	  for(int i=1;i<=m*2+10;i++,putchar('\n')) printf("from%d to%d dist%d",edge[i].fr,edge[i].to,edge[i].w);
	 
}
void dfs(int x)
{  
   for(int i=0;i<G[x].size();i++)
   { int v=edge[G[x][i]].to;
     if(f[x][0]==v) continue;
	 f[v][0]=x;
	 d[v]=d[x]+1;
	 w[v][0]=edge[G[x][i]].w;//printf("fa:%d son:%d",x,v);
	 dfs(v);
	 
   } 
}
void build()
{  maxi=(int)(log((double)n)/log(2.0))+1;
   for(int i=1;i<=maxi;i++)
    for(int k=1;k<=n;k++)
	   { f[k][i]=f[f[k][i-1]][i-1];
	     w[k][i]=min(w[k][i-1],w[f[k][i-1]][i-1]);
	   }
   
}
int query(int x,int y)
{   int ans=2147483647;// printf("start x=%d  y=%d d[x]=%d d[y]=%d  f[y][0]=%d\n",x,y,d[x],d[y],f[y][0]);
    if(d[x]<d[y]) swap(x,y);
    
	for(int j=maxi;j>=0;j--)
	{
		if(d[f[x][j]]>=d[y])
		{ ans=min(ans,w[x][j]);
		  x=f[x][j];
		}
	}
	
	for(int j=maxi;j>=0;j--)
	{
		 if(f[x][j]!=f[y][j])
		 {
		 	ans=min(ans,min(w[x][j],w[y][j]));
		 	x=f[x][j]; y=f[y][j];
		 }
	}
    if(x!=y) ans=min(ans,min(w[x][0],w[y][0]));
	return ans; 	
}
void work()
{
  
  //printf("23333\n");
 // build();
  int q;
  scanf("%d",&q);
  for(int i=1;i<=q;i++)
  {  
     int x,y;
     scanf("%d%d",&x,&y);
     if(gef(x)==gef(y))
     {   
         
     	 printf("%d\n",query(x,y));
     	 
     }
     else
     printf("-1\n");
  }
}
int main()
{
  freopen("truck.in","r",stdin);
  freopen("truck.out","w",stdout);
  init();
  krus();
  d[1]=1;
  dfs(1);
  build();
  work();
 // for(int i=1;i<=n;i++) printf("d[%d]=%d\n",i,d[i]);
  return 0;
}