记录编号	174744	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.197 s
提交时间	2015-08-02 20:27:37	内存使用	3.27 MiB

# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>

using namespace std;

const int MAXN = 10005;

int n,m,q;

void Swap(int &a,int &b){
	a ^= b;
	b ^= a;
	a ^= b;
}

struct Point {
	int u,v,w;
} t[MAXN << 3]; //最大生成树
bool comp(const Point &a,const Point &b) {
	return a.w > b.w;
}

int tot;
int head[MAXN];
struct Edge {
	int u,v,w,next;
} e[MAXN << 3]; //邻接表

void add(int u,int v,int w){
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].w = w;
	e[tot].next = head[u];
	head[u] = tot;
}

int fa[MAXN];//并查集
int find(int x) {
	if(fa[x] == x)
		return x;
	fa[x] = find(fa[x]);
	return fa[x];	
}

int deep[MAXN];//倍增求LCA
int f[MAXN][20];
int g[MAXN][20];

void dfs(int x,int d){
	deep[x] = d;
	for(int i = head[x];i;i = e[i].next){
		int v = e[i].v;
		if(!deep[v]){
			f[v][0] = x;
			g[v][0] = e[i].w;
			dfs(e[i].v,d+1);
		}
	}
} 

void pre_work(){
	for(int j = 1;(1 << j) <= n;++j)
		for(int i = 1;i <= n;++i){
			if(f[i][j - 1]){
				if(g[i][j - 1] < g[f[i][j - 1]][j - 1])
					g[i][j] = g[i][j - 1];
				else
					g[i][j] = g[f[i][j - 1]][j - 1];
				f[i][j] = f[f[i][j - 1]][j - 1];		
			}
		}
}

void work(int a,int b){
	int i,j;
	int ans = 0x3fffffff;
	for(i = 0;(1 << i) <= deep[a];++i);
	i--;
	for(j = i;j >= 0;j--){
		if(deep[a] - (1 << j) >= deep[b]){
			if(g[a][j] < ans) ans = g[a][j];
			a = f[a][j];
		}
	}
	if(a == b){
		printf("%d\n",ans);
		return ;
	}
	for(j = i;j >= 0;j--){
		if(f[a][j] && f[a][j] != f[b][j]){
			if(g[a][j] < ans) ans = g[a][j];
			if(g[b][j] < ans) ans = g[b][j];
			a = f[a][j];
			b = f[b][j];
		}
	}
	if(g[a][0] < ans) ans = g[a][0];
	if(g[b][0] < ans) ans = g[b][0];
	printf("%d\n",ans);
}

int main() {
	int i,j;
	freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i = 1; i <= n; ++i) fa[i] = i;
	for(i = 1; i <= m; ++i) scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].w);
	sort(t + 1, t + m + 1,comp);
	for(i = 1; i <= m; ++i) {
		int u = find(t[i].u);
		int v = find(t[i].v);
		if(u != v) {
			fa[v] = u;
			add(t[i].v,t[i].u,t[i].w);
			add(t[i].u,t[i].v,t[i].w);
		}
	}
	for(i = 1; i <= n; ++i)
		if(!deep[i])
			dfs(i,1);
	pre_work();	
	scanf("%d",&q);
	while(q--){
		int u,v;
		scanf("%d%d",&u,&v);
		if(find(u) != find(v)){
			printf("-1\n");
			continue;
		}
		if(deep[u] < deep[v])
			work(v,u);
		else
			work(u,v);	
	}
	return 0;
}
/*

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

*/