记录编号	521854	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.223 s
提交时间	2018-11-07 22:24:07	内存使用	4.46 MiB

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=10010;
const int maxm=50010;
int n,m,q;

struct ee{int u,v,w;}e[maxm];
inline bool cmp(ee a,ee b){return a.w>b.w;}
int bfa[maxn];
vector<int>t[maxn],w[maxn];
bool vis[maxn];
int val[maxn];
int tot,sz[maxn],fa[maxn],dep[maxn],son[maxn],top[maxn],id[maxn],pre[maxn];
inline int find(int x){return bfa[x]==x?x:bfa[x]=find(bfa[x]);}
inline void kruskal(){
	for(int i=1;i<=n;i++)bfa[i]=i;
	sort(e+1,e+m+1,cmp);
	int cnt=0;
	for(int i=1;i<=m;i++){
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v){
			cnt++;
			t[e[i].u].push_back(e[i].v);
			t[e[i].v].push_back(e[i].u);
			w[e[i].u].push_back(e[i].w);
			w[e[i].v].push_back(e[i].w);
			bfa[u]=v;
		}
		if(cnt==n-1)break;
	}
}

inline void dfs1(int u,int f,int d){
	sz[u]=1;fa[u]=f;dep[u]=d;vis[u]=true;
	int len=t[u].size();
	for(int i=0;i<len;i++){
		int v=t[u][i];
		if(v==f)continue;
		dfs1(v,u,d+1);
		val[v]=w[u][i];
		sz[u]+=sz[v];
		if(!son[u]||sz[son[u]]<sz[v])son[u]=v;
	}
}
inline void dfs2(int u,int tou){
	top[u]=tou;id[u]=++tot;pre[tot]=u;
	if(!son[u])return ;
	dfs2(son[u],tou);
	int len=t[u].size();
	for(int i=0;i<len;i++){
		int v=t[u][i];
		if(v!=fa[u]&&v!=son[u])dfs2(v,v);
	}
}

int minn[maxn<<2];
inline void build(int o,int l,int r){
	if(l==r){
		minn[o]=val[pre[l]];
		return;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	build(ls,l,m);
	build(rs,m+1,r);
	minn[o]=min(minn[ls],minn[rs]);
}
inline int findmin(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return minn[o];
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	int ans=0x3f3f3f3f;
	if(m>=nl)ans=min(ans,findmin(ls,l,m,nl,nr));
	if(m<nr)ans=min(ans,findmin(rs,m+1,r,nl,nr));
	return ans;
}
inline void getans(int x,int y){
	int u=top[x],v=top[y];
	int ans=0x3f3f3f3f;
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v),swap(x,y);
		ans=min(ans,findmin(1,1,tot,id[u],id[x]));
		//cout<<ans<<" "<<findmin(1,1,n,id[x],id[u])<<endl;
		x=fa[u];u=top[x];
	}
	if(dep[x]<dep[y])swap(x,y);
	if(x!=y)ans=min(ans,findmin(1,1,tot,id[son[y]],id[x]));
	//cout<<id[x]<<" "<<id[y]<<endl;
	if(ans==0x3f3f3f3f)puts("-1");
	else printf("%d\n",ans);
}
int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++){
		e[i].u=read(),e[i].v=read(),e[i].w=read();
	}
	kruskal();
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			val[i]=0x3f3f3f3f;
			dfs1(i,0,1);
			dfs2(i,i);
		}
	}
	q=read();
	build(1,1,tot);
	for(int i=1;i<=q;i++){
		int x=read(),y=read();
		getans(x,y);
	}
	return 0;
}