记录编号	420998	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2017-07-06 05:24:00	内存使用	1.51 MiB

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#define maxn 10010
#define maxm 50010
using namespace std;
struct edge{
	int to,cost;
};
int asdd=1;
struct Edge{
	int from,to,cost;
};
int ffread(){
	int p=0;
	int c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) p=(p<<1)+(p<<3)+(c^48);
	return p;
}
int fa[maxn],Basis[maxn],Cost[maxn],seg[4*maxn],depth[maxn],paa[maxn],topp[maxn],hson[maxn],Mark[maxn],liantongkuai[maxn];
int Sea(int p){
	if(fa[p]!=p)
	return fa[p]=Sea(fa[p]);
	return p;
}
vector<edge>G[maxn];
void addedge(int from,int to,int cost){
	G[from].push_back((edge){to,cost
	});
	G[to].push_back((edge){from,cost
	});
}
Edge asd[maxm];
bool vis[maxn];
bool comp(const Edge&a ,const Edge &b){
	return a.cost>b.cost;
}
int DFS1(int u,int pa,int dep){
	vis[u]=1;
	paa[u]=pa;
	depth[u]=dep;
	liantongkuai[u]=asdd;
	int k=0,tot=0;
	for(int i=0;i<G[u].size();i++){
		edge &e=G[u][i];
		int v=e.to;
		if(v==pa)
		continue;
		Cost[v]=e.cost;
		int b=DFS1(v,u,dep+1);
		if(b>k){
			k=b;
			hson[u]=v;
		}
		tot+=k;
	}
	return tot+1;
}
int sv=0;
int DFS2(int u,int top){
	Mark[u]=sv;
	topp[u]=top;
	Basis[sv]=Cost[u];
	sv++;
	if(hson[u]){
		DFS2(hson[u],top);
	}
	for(int i=0;i<G[u].size();i++){
		edge &e=G[u][i];
		int v=e.to;
		if(v==paa[u]||v==hson[u])
		continue;
		DFS2(v,v);
	}
}
int build(int l,int r,int o){
	if(l==r)
	return seg[o]=Basis[l];
	int mid=(l+r)/2;
	return seg[o]=min(build(l,mid,o<<1),build(mid+1,r,o<<1|1));
}
int query(int l,int r,int o,int ll,int rr){
	if(ll<=l&&rr>=r)
	return seg[o];
	int mid=(l+r)/2;
	int ans=999999999;
	if(ll<=mid)
	ans=min(ans,query(l,mid,o<<1,ll,rr));
	if(rr>mid)
	ans=min(ans,query(mid+1,r,o<<1|1,ll,rr));
	return ans;
}
int ask(int u,int v){
	int ans=999999999;
	while(topp[u]!=topp[v]){
		if(depth[topp[u]]<depth[topp[v]])
		swap(u,v);
		ans=min(ans,query(0,sv-1,1,Mark[topp[u]],Mark[u]));
		u=paa[topp[u]];
	}
	if(depth[u]<depth[v])
	swap(u,v);
	if(u!=v)
	ans=min(ans,query(0,sv-1,1,Mark[v]+1,Mark[u]));
	return ans;
}
void init(){
	int n,m;
	n=ffread(),m=ffread();
	for(int i=1;i<=n;i++)
	fa[i]=i;
	for(int i=0;i<m;i++){
		int from,to,cost;
		from=ffread(),to=ffread(),cost=ffread();
		asd[i]=(Edge){from,to,cost
		};
		//cout<<cost<<endl;
	}
	sort(asd,asd+m,comp);
	for(int i=0;i<m;i++){
		int from=asd[i].from,to=asd[i].to;
		int paa=Sea(from),pbb=Sea(to);
		if(paa!=pbb){
			bool taa=rand();
			if(taa)
			fa[paa]=pbb;
			else 
			fa[pbb]=paa;
			addedge(from,to,asd[i].cost);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			DFS1(i,-1,0);
			DFS2(i,i);
			asdd++;
		}
	}
	build(0,sv-1,1);
	int q;
	q=ffread();
	for(int i=0;i<q;i++){
		int u,v;
		u=ffread(),v=ffread();
		if(liantongkuai[u]!=liantongkuai[v])
		cout<<-1;
		else
		cout<<ask(u,v);
		cout<<endl;
	}
}
int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	srand(time(NULL));
	init();
}