记录编号	204244	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2015-11-04 07:52:21	内存使用	3.53 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
#define file
#define rep(i, l, r) for (long long i = (l); i <= (r); ++i)

using namespace std;
typedef vector<long long> vll;
const long long MAXM(50010);
struct tree {
	long long u, v, w;
} edge[MAXM];

const long long MAXN(10010), INF(LLONG_MAX / 3);
long long n,m,as[MAXN],ufs(long long),fa[MAXN],cost[MAXN],anc[MAXN][10],
dig[MAXN],maxcost[MAXN][10],q;
bool cmp(const tree&, const tree&), vis[MAXN];
vector<long long> gtv[MAXN], gtu[MAXN];
void build_tree(long long);
inline void preprocess();
inline long long read(), query(long long, long long);

int main() {
#ifdef file
	freopen("truck.in", "r", stdin);
	freopen("truck.out", "w", stdout);
#endif
	n = read();
	m = read();
	rep(i, 1, m) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w = read();
	}
	sort(edge + 1, edge + m + 1, cmp);
	rep(i, 1, n)
		as[i] = i;
	long long cnt = 0;
	rep(i, 1, m) {
		long long fx = ufs(edge[i].u), fy = ufs(edge[i].v);
		if (fx != fy) {
			gtv[edge[i].u].push_back(i);
			gtu[edge[i].v].push_back(i);
			as[fx] = fy;
			++cnt;
			if (cnt >= n - 1)
				break;
		}
	}
	rep(i, 1, n)
		if (! vis[i]) {
			dig[i] = 0;
			build_tree(i);
		}
	preprocess();
	for (q = read(); q; --q) {
		long long x, y;
		x = read();
		y = read();
		printf("%lld\n", query(x, y));
	}
//	for (; ; );
}

bool cmp(const tree &a, const tree &b) {
	return a.w > b.w;
}

long long ufs(long long x) {
	return (x == as[x]) ? x : (as[x] = ufs(as[x]));
}

void build_tree(long long root) {
	vis[root] = true;
	for (vll::iterator it = gtv[root].begin(); it != gtv[root].end(); ++it)
		if (! vis[edge[*it].v]) {
			cost[edge[*it].v] = edge[*it].w;
			fa[edge[*it].v] = root;
			dig[edge[*it].v] = dig[root] + 1;
			build_tree(edge[*it].v);
		}
	for (vll::iterator it = gtu[root].begin(); it != gtu[root].end(); ++it)
		if (! vis[edge[*it].u]) {
			cost[edge[*it].u] = edge[*it].w;
			fa[edge[*it].u] = root;
			dig[edge[*it].u] = dig[root] + 1;
			build_tree(edge[*it].u);
		}
}

inline void preprocess() {
	for (long long i = 1; i <= n; ++i) {
		anc[i][0] = fa[i];
		maxcost[i][0] = cost[i];
		for (long long j = 1; (1 << j) < n; ++j)
			anc[i][j] = -1;
	}
	for (long long j = 1; (1 << j) < n; ++j)
		for (long long i = 1; i <= n; ++i)
			if (anc[i][j - 1] != -1) {
				long long a = anc[i][j - 1];
				anc[i][j] = anc[a][j - 1];
				maxcost[i][j] = min(maxcost[i][j - 1], maxcost[a][j - 1]);
			}
}

inline long long read() {
	long long x = 0;
	char c;
	while (! isdigit(c = getchar()));
	while (isdigit(c)) {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x;
}

inline long long query(long long p, long long q) {
	if (ufs(q) != ufs(p))
		return -1;
	long long log;
	if (dig[p] < dig[q])
		swap(p, q);
	for (log = 1; (1 << log) <= dig[p]; ++log);
	--log;
	long long ans = INF;
	for (long long i = log; i >= 0; --i)
		if (dig[p] - (1 << i) >= dig[q]) {
			ans = min(ans, maxcost[p][i]);
			p = anc[p][i];
		}
	if (p == q)	//LCA->p
		return ans;
	for (long long i = log; i >= 0; --i)
		if (anc[p][i] != -1 && anc[p][i] != anc[q][i]) {
			ans = min(ans, maxcost[p][i]);
			p = anc[p][i];
			ans = min(ans, maxcost[q][i]);
			q = anc[q][i];
		}
	ans = min(ans, cost[p]);
	ans = min(ans, cost[q]);
	return ans;	//LCA->fa[p]
}