记录编号	270575	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2016-06-15 07:58:22	内存使用	2.92 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include <cctype>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("truck.in","r",stdin);freopen("truck.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=10010;
int n=0,m=0,ri=0,rr=0,q=0,deep;
int fath[maxn]={0},d[maxn]={0};
int find(int x){
	if(fath[x]!=x)fath[x]=find(fath[x]);
	return fath[x];
} 
bool onion(int x,int y){
	ri=find(x);rr=find(y);
	if(ri==rr)return 0;
	else{
		fath[rr]=ri;
		return 1;
	}
}
void swap(int &x,int &y){
	int z=x;
	x=y;
	y=z;
}
int getint(){
	int ret,neg;
	char ch;
	ret=neg=0;
	while(!isdigit(ch=getchar())&&ch!='-');
	if(ch=='-')neg=1,ch=getchar();
	while(ret=ret*10+ch-'0',isdigit(ch=getchar()));
	if(neg)ret=-ret;
	return ret;
}
struct node{
	int s,t,v;
	bool operator < (const node&b) const{
		return v>b.v;
	}
}e[(maxn<<2)+maxn];
struct data{
	int to,next,v;
}t[(maxn<<1)+maxn];
int head[(maxn<<1)+maxn];
int tot=0;
inline void insert(int x,int y,int v){
	tot++;
	t[tot].to=y;
	t[tot].v=v;
	t[tot].next=head[x];
	head[x]=tot;
}
int w[maxn][20]={0},fa[maxn][20]={0};
void build(int x,int dp){
	d[x]=dp;
	for(int i=head[x];i;i=t[i].next){
		int y=t[i].to;
		if(!fa[y][0]){
			fa[y][0]=x;
			w[y][0]=t[i].v;
			build(y,dp+1);
		}
	}
}
int lca(int x,int y){
	int res=0x7fffffff;
	if(d[x]<d[y])swap(x,y);
	for(int j=deep-1;j>-1;j--){
		if(d[fa[x][j]]>=d[y]){
			res=min(res,w[x][j]);
			x=fa[x][j];
		}
	}
	if(x!=y){
		for(int j=deep-1;j>-1;--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]));
	}
	return res;
}
void chul(){
	n=getint();m=getint();
	deep=(int)(log((double)n)/log(2.0))+1;
	for(int i=1;i<=m;i++){
		e[i].s=getint();
		e[i].t=getint();
		e[i].v=getint();
	}
	sort(e+1,e+1+m);
	for(int i=1;i<=n;i++)fath[i]=i;
	for(int i=1;i<=m;i++){
		if(onion(e[i].s,e[i].t)){
			insert(e[i].s,e[i].t,e[i].v);
			insert(e[i].t,e[i].s,e[i].v);
		}
	}
	for(int i=1;i<=n;i++){
		if(!fa[i][0]){
			w[i][0]=0x7fffffff;
			fa[i][0]=i;
			build(i,1);
		}
	}
	for(int j=1;j<deep;j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
			w[i][j]=min(w[i][j-1],w[fa[i][j-1]][j-1]);
		}
	}
	q=getint();
	int x=0,y=0;
	for(int i=1;i<=q;i++){
		x=getint();y=getint();
		if(find(x)!=find(y))puts("-1");
		else printf("%d\n",lca(x,y));
	}
}
int main(){
	Begin;
}