记录编号	318305	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2016-10-09 08:09:00	内存使用	2.67 MiB

#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;

int n, m, q;
const int maxedge = 50100, maxnumber = 10100;
struct Edge
{
	int from, to, w, next;
}e[maxedge << 1], edges[maxnumber << 1];
int head[maxnumber], tot;
int root[maxnumber];
int weight[maxnumber];
int depth[maxnumber], size[maxnumber], fa[maxnumber], son[maxnumber];
int dfn[maxnumber], id[maxnumber], top[maxnumber], dfsclock;
int minn[maxnumber << 2];

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void Write(int a)
{
	int cnt = 0;
	char ch[50] = {'\0'};
	while(1){
		ch[++cnt] = a % 10 + '0';
		a /= 10;
		if(!a) break;
	}
	while(cnt) putchar(ch[cnt--]);
	puts("");
}

inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

int FindRoot(const int& a)
{
	if(root[a] != a) root[a] = FindRoot(root[a]);
	return root[a];
}

inline void Union(const int& a, const int& b)
{
	int ra = FindRoot(a), rb = FindRoot(b);
	root[ra] = rb;
}

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

inline void Kruskal()
{
	sort(e+1, e+1+m*2, cmp);
	int cnt = 0;
	for(int i = 1; i <= m * 2; i++){
		int from = e[i].from, to = e[i].to, w = e[i].w;
		if(FindRoot(from) != FindRoot(to)){
			Union(from, to);
			cnt++;
			AddEdge(from, to, w);
			AddEdge(to, from, w);
		}
		if(cnt == n - 1) return;
	}
}

void Segment_Tree_Build(const int& l, const int& r, const int& rt)
{
	if(l == r){
		minn[rt] = weight[id[l]];
		// printf("minn[%d]:%d ", rt, minn[rt]);
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	Segment_Tree_Build(l, mid, lch);
	Segment_Tree_Build(mid+1, r, rch);
	minn[rt] = min(minn[lch], minn[rch]);
}

int Segment_Tree_Min(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(s <= l && t >= r) return minn[rt];
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if(t <= mid) return Segment_Tree_Min(l, mid, lch, s, t);
	else if(s >= mid + 1) return Segment_Tree_Min(mid+1, r, rch, s, t);
	return min(Segment_Tree_Min(l, mid, lch, s, mid), Segment_Tree_Min(mid+1, r, rch, mid+1, t));
}

void DFS1(const int& a)
{
	size[a] = 1;
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to, w = edges[i].w;
		if(to == fa[a]) continue;
		depth[to]= depth[a] + 1;
		fa[to] = a;
		weight[to] = w;
		DFS1(to);
		if(size[to] > size[son[a]]) son[a] = to;
		size[a] += size[to];
	}
}

void DFS2(const int& a, const int& tp)
{
	top[a] = tp;
	dfn[a] = ++dfsclock;
	id[dfsclock] = a;
	if(son[a]) DFS2(son[a], tp);
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[a] || to == son[a]) continue;
		DFS2(to, to);
	}
}

inline int Query_Min(int s, int t)
{
	int f1 = top[s], f2 = top[t], ret = 0x7fffffff;
	while(f1 != f2){
		if(depth[f1] < depth[f2]){
			swap(f1, f2);
			swap(s, t);
		}
		ret = min(ret, Segment_Tree_Min(1, n, 1, dfn[f1], dfn[s]));
		s = fa[f1];
		f1 = top[s];
	}
	if(s == t) return ret;
	if(depth[s] < depth[t]) swap(s, t);
	ret = min(ret, Segment_Tree_Min(1, n, 1, dfn[son[t]], dfn[s]));
	return ret;
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("truck.in", "r", stdin); freopen("truck.out", "w", stdout);
#endif

	memset(weight, 0x3f, sizeof(weight));
	Read(n); Read(m);
	int from, to, w, s, t, cnt = 0;
	for(int i = 1; i <= n; i++) root[i] = i;
	for(int i = 1; i <= m; i++){
		Read(from); Read(to); Read(w);
		e[++cnt].from = from; e[cnt].to = to; e[cnt].w = w;
		e[++cnt].from = to; e[cnt].to = from; e[cnt].w = w;
	}

	Kruskal();
	depth[1] = 1;
	DFS1(1);
	DFS2(1, 1);
	// for(int i = 1; i <= n; i++) printf("weight[%d]:%d n", i, weight[i]); printf("\n");
	Segment_Tree_Build(1, n, 1);

	Read(q);
	for(int i = 1; i <= q; i++){
		Read(s); Read(t);
		if(!dfn[s] || !dfn[t]) puts("-1");
		else Write(Query_Min(s, t));
	}

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}