记录编号	312956	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	coolkid	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2016-09-27 21:13:55	内存使用	3.11 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

const int MAXM=50010;
const int MAXN=10010;

struct Edge{
	int from,to,dist;
	bool operator < (const Edge &rhs) const {
		return dist>rhs.dist;
	}
}edges[MAXM],Edges[MAXN<<1];

int n,m,q;

void init(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++) scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].dist);
}

int fa[MAXN];
bool vis[MAXM];

int getfather(int x){ return fa[x]==x?x:fa[x]=getfather(fa[x]);}

vector<int> G[MAXN];
int Size=0;

void Kruskal(){
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(edges,edges+m);
	for(int i=0;i<m;i++){
		int x=edges[i].from,y=edges[i].to;
		int fax=getfather(x),fay=getfather(y);
		if(fax!=fay){
			fa[fax]=fay;
			vis[i]=true;
		}
	}
	for(int i=0;i<m;i++)if(vis[i]){
		Edge &e=edges[i];
		Edges[Size++]=(Edge){e.from,e.to,e.dist};
		Edges[Size++]=(Edge){e.to,e.from,e.dist};
		G[e.from].push_back(Size-2);
		G[e.to].push_back(Size-1);
	}
}

const int MAXLOG=23;

int prt[MAXN][MAXLOG],prtw[MAXN][MAXLOG],deep[MAXN],maxdepth;

void dfs(int u){
	for(int i=0;i<G[u].size();i++){
		Edge &e=Edges[G[u][i]];
		if(prt[u][0]==e.to) continue;
		deep[e.to]=deep[u]+1;
		prt[e.to][0]=u;prtw[e.to][0]=e.dist;
		dfs(e.to);
	}
}

void Build(){
	maxdepth=log(n)/(double)log(2.0);
	for(int j=1;j<=maxdepth;j++)
		for(int i=1;i<=n;i++){
			prt[i][j]=prt[prt[i][j-1]][j-1];
			prtw[i][j]=min(prtw[i][j-1],prtw[prt[i][j-1]][j-1]);
		}
}

const int INF=2147483647;

int Query(int x,int y){
	int ans=INF;
	if(deep[x]<deep[y]) swap(x,y);
	if(deep[x]>deep[y])
		for(int numstep=deep[x]-deep[y],j=0;numstep;numstep>>=1,j++)
			if(numstep&1)
				ans=min(ans,prtw[x][j]),x=prt[x][j];
	if(x!=y){
		while(1){
			int j=maxdepth;
			while(j>=0&&prt[x][j]==prt[y][j]) j--;
			if(j<0){
				ans=min(ans,min(prtw[x][0],prtw[y][0]));
				break;
			}
			else{
				ans=min(ans,min(prtw[x][j],prtw[y][j]));
				x=prt[x][j];y=prt[y][j];
			}
		}
	}
	return ans;
}
void work(){
	scanf("%d",&q);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		int fax=getfather(x),fay=getfather(y);	
		if(fax==fay){
			printf("%d\n",Query(x,y));
		}
		else printf("-1\n");
	}
}

int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	init();
	Kruskal();
	dfs(1);
	Build();
	work();
	#ifdef DEBUG
		for(int i=1;i<=n;i++,putchar('\n'))
		    for(int j=0;j<=maxdepth;j++) printf("%d ",prtw[i][j]);
		while(1);
	#endif
	return 0;
}