记录编号	445558	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	Ays	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2017-09-06 12:55:11	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,q;
struct ro{
	int to,v;
};
vector<ro> a[10005];
struct roold{
	int qq,ww,v;
};
roold old[50005];
int father[10005];
struct rule{
	bool operator ()(const roold &s1,const roold &s2){
		return s1.v>s2.v;
	}
};
int find(int now){
	if(father[now]==now) return now;
	return father[now]=find(father[now]);
}
void maxtree(){
	for(int i=1;i<=n;i++) father[i]=i;
	for(int i=1;i<=m;i++){
		int s1=find(old[i].qq);
		int s2=find(old[i].ww);
		if(s1==s2) continue;
//		printf("---%d %d v:%d\n",old[i].qq,old[i].ww,old[i].v);
//		printf("*\n");
		ro ss;
		father[s1]=s2;
		ss.to=s2;ss.v=old[i].v;
		a[s1].push_back(ss);ss.to=s1;
		a[s2].push_back(ss);
	}
}

void sc(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int s1,s2,quan;
		scanf("%d%d%d",&s1,&s2,&quan);
		roold ss;ss.qq=s2;ss.v=quan;ss.ww=s1;
		old[i]=ss;
	}
	sort(old+1,old+1+m,rule());
}
int fa[10005][20],deep[10005],f[10005][20];

int ask(int x,int fat){
	int mn=0x7fffffff;
	int t=deep[x]-deep[fat];
	for(int i=14;i>=0;i--){
		if ((1<<i)> deep[x]-deep[fat]) continue;
		mn=min(mn,f[x][i]);
		x=fa[x][i];
	}
	return mn;
}

int lca(int x,int y){
//	int minn=0x7fffffff;
	if(deep[x]<deep[y])swap(x,y);// make x is deeper
	for(int i=14;i>=0;i--){
		if(deep[y]<=deep[fa[x][i]]){
			x=fa[x][i];
//			minn=min(minn,f[y][i]);
		}
	}
	if(x==y) return x;
	for(int i=14;i>=0;i--){
		if(fa[y][i]!=fa[x][i]){
			y=fa[y][i];x=fa[x][i];
//			minn=min(minn,f[y][i]);
//			minn=min(minn,f[x][i]);
		}
	}
//	minn=min(minn,f[x][0]);
//	return minn;
	return fa[x][0];
}

void dfs(int now,int fat,int d){
	deep[now]=d;
	fa[now][0]=fat;
	for(int i=1;i<=14;i++){
	//	printf("%d++",i);
		f[now][i]=min(f[fa[now][i-1]][i-1],f[now][i-1]);
	//	printf("*");
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=0;i<a[now].size();i++){
//		printf("%d %d****\n",a[now][i].to,fat);
		if(a[now][i].to!=fat){
		f[a[now][i].to][0]=a[now][i].v;
//		printf("%d %d--------\n",a[now][i].v,now);
		dfs(a[now][i].to,now,d+1);
		}
		
	}
}
void sc2(){
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int x,y;scanf("%d%d",&x,&y);
		if(find(x)!=find(y)){
			printf("-1\n");
			continue;
		}
		int q1=lca(x,y);
//		if(x==4&&y==3) printf("*%d ",lca(x,y));
		printf("%d\n",min(ask(x,q1),ask(y,q1)));
//		printf("%d %d\n",ask(x,q1),ask(y,q1));
	}
}


int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	sc();
	memset(f,127,sizeof(f));
	maxtree();
	dfs(1,1,0);
	sc2();
	return 0;
}
/*
10 24
4 7 19038
7 10 7375
7 9 17853
9 8 6341
7 2 16976
10 3 2835
10 4 19285
9 4 29193
3 4 4852
3 8 16597
9 1 4138
9 7 21611
7 4 10586
10 4 7821
10 9 25636
3 9 28425
2 3 17229
4 8 11331
9 2 25053
6 4 929
8 3 1738
10 9 28542
1 2 28343
3 5 13215
9
7 5
2 4
10 2
5 10
7 10
4 3
10 1
10 4
8 4
*/