记录编号	296724	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2016-08-15 21:18:48	内存使用	1.50 MiB

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int read(){
	int x=0,f=1; char ch = getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch = getchar();
	}
	while(ch>='0'&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*f;
}
const int maxn = 10010, maxm = 50010;
struct Edge{
	int from, to, dis;
	bool operator < (const Edge& x) const {
		return dis > x.dis;
	}
	Edge(int t=0, int d=0){
		from = 0; to = t; dis = d;
	}
}e[maxm];
vector<Edge> G[maxn];
void Add_Edge(int u, int v, int w){ 
	G[u].push_back(Edge(v, w));
}
int N, M, Q;
int size[maxn], depth[maxn], fa[maxn], son[maxn], va[maxn];
void dfs1(int x){
	// printf("%d ", x);
	size[x] = 1;
	for(int i=0; i<(int)G[x].size(); ++i){
		int to = G[x][i].to;
		if(size[to]) continue;
		// printf("TO-->%d\n", to);
		fa[to] = x; depth[to] = depth[x]+1; va[to] = G[x][i].dis;
		dfs1(to);
		size[x] += size[to];
		if(size[to] > size[son[x]]) son[x] = to;
	}
} 
int dfn[maxn], top[maxn], tonode[maxn], dfn_cnt;
void dfs2(int x, int tp){
	dfn[x] = ++dfn_cnt; tonode[dfn_cnt] = x;
	top[x] = tp;
	if(son[x]) dfs2(son[x], tp);
	for(int i=0; i<(int)G[x].size(); ++i){
		int to = G[x][i].to;
		if(!dfn[to]) dfs2(to, to);
	}
}

int minn[maxn<<2], s, t;
void Build(int rt, int l, int r){
	if(l==r){
		minn[rt] = va[tonode[l]];
		// printf("BUILD %d %d %d\n", l, r, minn[rt]);
		return;
	}
	int lc = rt<<1, rc = rt<<1|1, mid = (l+r)>>1;
	Build(lc, l, mid);
	Build(rc, mid+1, r);
	minn[rt] = min(minn[lc], minn[rc]);
		// printf("BUILD %d %d %d\n", l, r, minn[l]);
}
int Query(int rt, int l, int r){
	if(s<=l && r<=t) return minn[rt];
	int lc = rt<<1, rc = rt<<1|1, mid = (l+r)>>1;	
	int minnum = 0x3f3f3f3f;
	if(s<=mid) minnum = min(minnum, Query(lc, l, mid));
	if(t>mid)  minnum = min(minnum, Query(rc, mid+1, r));
	return minnum;
}

int QueryT(int x, int y){
	int minnum = 0x3f3f3f3f;
	while(top[x]!=top[y]){
		if(depth[top[x]] < depth[top[y]]) swap(x, y);
		s = dfn[top[x]], t = dfn[x];
		// printf("---->%d %d\n", s, t);
		minnum = min(minnum, Query(1, 1, N));
		x = fa[top[x]];
	}
	if(depth[x] < depth[y]) swap(x, y);
	s = dfn[y]+1, t = dfn[x];
		// printf("---->%d %d\n", s, t);
	return minnum = min(minnum, Query(1, 1, N));
}

int f[maxn];
int find(int x){ return (f[x]==x)?x:f[x]=find(f[x]); }
void Kruskal(){
	sort(e+1, e+M+1);
	for(int i=1; i<=N; ++i) f[i] = i;
	for(int i=1, cnt=0; i<=M; ++i){
		int fa = find(e[i].from), fb = find(e[i].to);
		if(fa==fb) continue;
		Add_Edge(e[i].from, e[i].to, e[i].dis);
		Add_Edge(e[i].to, e[i].from, e[i].dis);
		f[fb] = fa;
		if(++cnt==N-1) return;
	}
}
int main(){
    freopen("truck.in","r",stdin); freopen("truck.out","w",stdout);
	N = read(), M = read(); 
	for(int i=1; i<=M; ++i) e[i].from = read(), e[i].to = read(), e[i].dis = read();
	Kruskal();
// puts("EDGE");
// 	for(int i=1; i<=N; ++i)
// 		for(int j=0; j<(int)G[i].size(); ++j)
// 			printf("%d %d %d\n", i, G[i][j].to, G[i][j].dis);
// puts("DFS1");
	for(int i=1; i<=N; ++i) if(f[i]==i) dfs1(i), dfs2(i, i);
// puts("DFN");
	// for(int i=1; i<=N; ++i) printf("%d ", son[i]); puts("");
	// for(int i=1; i<=N; ++i) printf("%d ", tonode[i]); puts("");
	// for(int i=1; i<=N; ++i) printf("%d ", va[i]); puts("");
		// puts("END1");
	Build(1, 1, N); 
	s = 1, t = N;
	// printf("%d\n", Query(1, 1, N));
		// puts("END2");
	Q = read();
	for(int i=1, x, y; i<=Q; ++i){
		x = read(), y = read();
		if(find(x)!=find(y)) puts("-1");
		else printf("%d\n", QueryT(x, y));
	}
	// while(1);
	return 0;
}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
 */