记录编号	138249	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2014-11-05 19:44:04	内存使用	2.50 MiB

/*
	author  :hzoi_天翔
	title   :[NOIP2013]货车运输
	ALG     :最大生成树 LCA 倍增
	comment :先用最大生成树选择一些边，再用倍增的 LCA 求出 RMQ
*/

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>

#define  maxn  10010
#define  maxm  50010
#define  maxk  17
#define  info  0x7fffffff

struct Edge{
	int next , to , len ;
	bool operator () (const int NEXT,const int TO,const int LEN) {
		this->next=NEXT ; this->to=TO ; this->len=LEN ;
	}
	bool operator < (const Edge b) const {
		return len > b.len ;
	}
	Edge() { next = to = len = 0 ; }
} E0[maxm] , E[maxn*2] ; int star[maxn] = {0} , tot = 0 ;

int n , m , q , cnt = 0 ;
int x , y , z ;

int k0 , k ;
//std::map<int,int> father , deep ;
int father[maxn] = {0} ;
int deep[maxn] = {0} ;
int fa[maxn][maxk] = {0} , w[maxn][maxk] ;

char ch ;
inline void qread(int & ret) {
	ret = 0 ; while (ch=getchar() , ch<'!') ;
	while (ret=ret*10+ch-'0' , ch=getchar() , ch>'!') ;
}

int min(const int a , const int b) {
	return a < b ? a : b ;
}

void exchange(int & a , int & b) {
	z = a ; a = b ; b = z ;
}

void addEdge(const Edge a) {
	x = a.next ; y = a.to ; z = a.len ;
	tot ++ ; E[tot](star[x] , y , z) ; star[x] = tot ;
	tot ++ ; E[tot](star[y] , x , z) ; star[y] = tot ;
}

int Find(int x) {
	return father[x] == 0 ? x : father[x] = Find(father[x]) ;
}

bool Union(const Edge a) {
	x = Find(a.next) ; y = Find(a.to) ;
	if (x == y) return false ;
	father[x] = y ; return true ;
}

void dfs(int p , int d) {
	//进入抢 father 环节
	//因为最大生成树是树，所以可以dfs求father
	deep[p] = d ;
	int i = star[p] ;
	while (i) {
		if (!fa[E[i].to][0]) {
			fa[E[i].to][0] = p ;
			w[E[i].to][0] = E[i].len ;
			dfs(E[i].to , d+1) ;
		}
		i = E[i].next ;
	}
}

int query(int u , int v) {
	if (Find(u) != Find(v)) return -1 ;

	int ret = info ;
	if (deep[u] < deep[v]) exchange(v , u) ;
	//使得u的深度最大
	for (k = k0-1 ; k >= 0 ; k -- )
		if (deep[fa[u][k]] >= deep[v]) {
			ret = min(ret , w[u][k]) ; u = fa[u][k] ;
		}
	//将u上浮和v调整到同一深度
	if (u != v) {
		for (k = k0-1 ; k >= 0 ; k -- )
			if (fa[u][k] != fa[v][k]) {
				ret = min(ret , min(w[u][k],w[v][k])) ;
				u = fa[u][k] ; v = fa[v][k] ;
			}
		ret = min(ret , min(w[u][0],w[v][0])) ;
	}
	//如果 u 与 v 不等，则用倍增法将u与v一同上浮到它们的 LCA 下方
	//的两个节点，再同时上浮一个节点就找到了 LCA
	return ret ;
}

int main() {
	#define  READ
	#ifdef   READ
		freopen("truck.in" ,"r",stdin ) ;
		freopen("truck.out","w",stdout) ;
	#endif

	qread(n) ; qread(m) ;
	for (int i = 0 ; i < m ; i ++ ) {
		qread(E0[i].next) ; qread(E0[i].to) ; qread(E0[i].len) ;
	}
	//构建最大生成树
	std::sort(E0 , E0+m) ;
	for (int i = 0 ; i<m && cnt<n-1 ; i ++ ) if (Union(E0[i])) {
		cnt ++ ; addEdge(E0[i]) ;
	}
	for (int p = 1 ; p <= n ; p ++ ) if (!fa[p][0]) {
		w[p][0] = info ; fa[p][0] = p ; dfs(p , 1) ;
	}

	//进行倍增的预处理
	k0 = (int)(log((double)n)/log(2.0))+1 ;
	for (int k = 1 ; k < k0 ; k ++ )
		for (int p = 1 ; p <= n ; p ++ ) {
			fa[p][k] = fa[ fa[p][k-1] ][k-1] ;
			w[p][k] = min(w[p][k-1] , w[ fa[p][k-1] ][k-1]) ;
		}

	//查询
	qread(q) ;
	while ( q -- ) {
		qread(x) ; qread(y) ;
		printf("%d\n" , query(x , y)) ;
	}

	return 0 ;
}