记录编号	408179	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.107 s
提交时间	2017-05-23 21:21:39	内存使用	1.74 MiB

# include <bits/stdc++.h>
# define mid ((l + r) >> 1)
# define MAXN 10023
# define MAXM 50023
using namespace std;

inline int gn() {
	int k = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

struct ed {
	int fr, to, w, ne;
	inline ed() {;}
	inline ed(int fr_, int to_, int w_, int ne_) {
		fr = fr_, ne = ne_, w = w_, to = to_;
	}
}e[MAXM];

inline bool cmp(ed a, ed b) {
	return a.w > b.w;
}

int hed[MAXN], ct;


inline void addedge(int fr, int to, int w) {
	e[++ct] = ed(fr, to, w, hed[fr]), hed[fr] = ct;
}

struct edge {
	int to, w;
	edge *ne;
	inline edge() {
		to = w = 0;
		ne = NULL;
	}
	inline edge(int to_, int w_, edge *ne_) {
		to = to_, w = w_, ne = ne_;
	}
}*head[MAXN];

inline void add_edge(int fr ,int to, int w) {
	edge *x = new edge(to, w, head[fr]);
	head[fr] = x;
	edge *y = new edge(fr, w, head[to]);
	head[to] = y;
}

int n, m, intree[MAXN], cnt;

int u[MAXN];

int get_fa(int x) {
	if(x == u[x]) return x;
	else return u[x] = get_fa(u[x]);
}

inline void merge(int x, int y) {
	x = get_fa(x), y = get_fa(y);
	u[y] = x;
}

inline void kruscal() {
	for(int i = 1;i <= n; i++) u[i] = i;
	sort(e + 1, e + m + 1, cmp);
	for(int i = 1; i <= m; i++) {
		int x = e[i].fr, y = e[i].to;
		if(get_fa(x) == get_fa(y)) continue;
		add_edge(x, y, e[i].w);
		merge(x, y);
	}
}

int dep[MAXN], fa[MAXN], siz[MAXN], que[MAXN], son[MAXN], a[MAXN];
bool vis[MAXN];

inline void bfs(int s) {
	memset(que, 0, sizeof(que));
	int l = 1, r = 1;
	que[1] = s;
	while(l <= r) {
		int u = que[l++];
		vis[u] = 1;
		siz[u] = 1, dep[u] = dep[fa[u]] + 1;
		for(edge *e = head[u]; e; e = e->ne) {
			if(e->to != fa[u]) a[e->to] = e->w, fa[e->to] = u, que[++r] = e->to;
		}
	}
	for(int i = r; i; i--) {
		siz[fa[que[i]]] += siz[que[i]];
		if(siz[que[i]] > siz[son[fa[que[i]]]]) son[fa[que[i]]] = que[i];
	}
}

int dfn[MAXN], adfn[MAXN], ids, top[MAXN];

void dfs(int x, int tp) {
	top[x] = tp;
	dfn[x] = ++ids;
	adfn[ids] = x;
	if(!~son[x]) return;
	dfs(son[x], tp);
	for(edge *e = head[x]; e; e = e->ne) {
		if(dfn[e->to]) continue;
		dfs(e->to, e->to);
	}
}

int mi[MAXN << 2], M;

inline void build() {
	memset(mi, 127, sizeof(mi));
	for(M = 1; M <= n + 1; M <<= 1);
	for(int i = 1; i <= n; i++) {
		mi[i + M] = a[adfn[i]];
	}
	for(int i = M; i >= 1; i--) {
		mi[i] = min(mi[i << 1], mi[i << 1 | 1]);
	}
}

inline int query(int l, int r) {
	int ans = 0x7fffffff;
	for(l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>=1) {
		if(~l & 1) ans = min(ans, mi[l + 1]);
		if(r & 1) ans = min(ans, mi[r - 1]);
	}
	return ans;
}

inline int get_ans(int u, int v) {
	int tu = top[u], tv = top[v];
	int ans = 0x7fffffff;
	while(tu ^ tv) {
		if(dep[tu] < dep[tv]) {	//保证u在v下面
			swap(tu, tv);
			swap(u, v);
		}
		ans = min(query(dfn[tu], dfn[u]), ans);
		u = fa[tu];
		tu = top[u];
	}
	if(u ^ v) {
		if(dep[u] > dep[v]) {
			swap(tu, tv);
			swap(u, v);
		}
		ans = min(query(dfn[son[u]], dfn[v]), ans);
	}
	return ans;
}

// u = 3, v = 1
//

int main() {
	//freopen("in.txt", "r", stdin);
	freopen("truck.in", "r", stdin);
	freopen("truck.out", "w", stdout);
	n = gn();
	m = gn();
	for(int i = 1; i <= m; i++) {
		int a = gn();
		int b = gn();
		addedge(a, b, gn());
	}
	kruscal();
	memset(son, -1, sizeof(son));
	for(int i = 1; i <= n; i++) {
		if(vis[i]) continue;
		bfs(i);
		dfs(i, i);
	}
	build();
	//for(int i = 1; i <= n; i++) printf("%d : dfn : %d top %d\n", i, dfn[i], top[i]);
	//for(int i = 1; i <= n; i++) printf("%d ", a[adfn[i]]);
	//printf("\n");
	///*
	int q = gn();
	while(q--) {
		int u = gn();
		int v = gn();
		if(get_fa(u) ^ get_fa(v)) printf("-1\n");
		else printf("%d\n", get_ans(u, v));
	}
	//*/
	//cout << query(3, 4);
}