记录编号	468459	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	WHZ0325	是否通过	通过
代码语言	C++	运行时间	0.141 s
提交时间	2017-11-01 10:27:55	内存使用	1.53 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int maxn=10005;
struct edge {int u,v,l;};
int n,m;
vector<edge> edges;
vector<edge> g[maxn];
int pa[maxn];
void init_set() {
	for(int i=1;i<=n;++i) {
		pa[i]=i;
	}
}
int find_set(int x) {
	int root=x;
	while(pa[root]!=root) {
		root=pa[root];
	}
	while(pa[x]!=root) {
		int t=pa[x];
		pa[x]=root;
		x=t;
	}
	return root;
}
void union_set(int x,int y) {
	pa[find_set(x)]=find_set(y);
}
bool same(int x,int y) {
	return find_set(x)==find_set(y);
}
bool cmp(edge a,edge b) {
	return a.l>b.l;
}
void kruskal() {
	init_set();
	sort(edges.begin(),edges.end(),cmp);
	for(int i=0;i<edges.size();++i) {
		if(!same(edges[i].u,edges[i].v)) {
			union_set(edges[i].u,edges[i].v);
			g[edges[i].u].push_back(edges[i]);
			g[edges[i].v].push_back((edge){edges[i].v,edges[i].u,edges[i].l});
		}
	}
}
int depth[maxn],tot[maxn],fa[maxn],son[maxn],d[maxn];
void dfs1(int x) {
	tot[x]=1;
	for(int i=0;i<g[x].size();++i) {
		if(!fa[g[x][i].v]) {
			fa[g[x][i].v]=x;
			depth[g[x][i].v]=depth[x]+1;
			d[g[x][i].v]=g[x][i].l;
			dfs1(g[x][i].v);
			tot[x]+=tot[g[x][i].v];
			if(tot[g[x][i].v]>tot[son[x]]) {
				son[x]=g[x][i].v;
			}
		}
	}
}
int ys[maxn],yss[maxn],lin[maxn],tag=0;
void dfs2(int x) {
	ys[yss[x]=++tag]=x;
	if(yss[x]==yss[fa[x]]+1) {
		lin[x]=lin[fa[x]];
	}
	else {
		lin[x]=x;
	}
	if(son[x]) {
		dfs2(son[x]);
	}
	for(int i=0;i<g[x].size();++i) {
		if(g[x][i].v!=fa[x]&&g[x][i].v!=son[x]) {
			dfs2(g[x][i].v);
		}
	}
}
int st[maxn][20];
void init_st() {
	for(int i=1;i<=n;++i) {
		st[i][0]=d[ys[i]];
	}
	for(int j=1;(1<<j)<=n;++j) {
		for(int i=1;i+(1<<j)-1<=n;++i) {
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r) {
	int k=0;
	while((1<<(k+1))<=(r-l+1)) {
		k++;
	}
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
int get_min(int x,int y) {
	int ans=INT_MAX;
	while(lin[x]!=lin[y]) {
		if(depth[lin[x]]<depth[lin[y]]) {
			swap(x,y);
		}
		ans=min(ans,query(yss[lin[x]],yss[x]));
		x=fa[lin[x]];
	}
	if(depth[x]<depth[y]) {
		swap(x,y);
	}
	if(x!=y) {
		ans=min(ans,query(yss[y]+1,yss[x]));
	}
	return ans;
}
int main() {
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	scanf("%d%d",&n,&m);
	int u,v,l;
	for(int i=0;i<m;++i) {
		scanf("%d%d%d",&u,&v,&l);
		edges.push_back((edge){u,v,l});
	}
	kruskal();
	fa[1]=depth[1]=1;
	dfs1(1);
	dfs2(1);
	init_st();
	int q;
	scanf("%d",&q);
	while(q--) {
		scanf("%d%d",&u,&v);
		if(same(u,v)) {
			printf("%d\n",get_min(u,v));
		}
		else {
			printf("-1\n");
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}