记录编号	158680	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.731 s
提交时间	2015-04-16 20:19:22	内存使用	12.66 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
class miku
{
public:
	int to;int lo;
};
deque<miku> in[50001],bt[10001];
class miku2
{
public:
	int wi,num;
};
deque<miku2>  p[30001];
class miku3
{
public:
	int t1,t2,num;
};
deque<miku3> dark;
int cnt=0;
int n,m,root[10001]={0},co[10001]={0},q,ans[30001]={0},f[10001],be[10001]={0};
int dfs(int i,int k)
{
	deque<int> q;
	int v=9999999,to=0,fr=0;
	q.push_back(i);
	//cout<<1<<endl;
	do
	{
		v=0,to=0,fr=0;
		for(int j=0;j<q.size();j++)
		{
			int x=q[j];
			for(int p=0;p<in[x].size();p++)
			{
				miku u=in[x][p];
				if(co[u.to]==0&&u.lo>v)
				{
					v=u.lo;to=u.to;fr=x;
				}
			}
		}
		if(to!=0)
		{
			//cout<<co[to]<<endl;
			miku x;
			x.to=to,x.lo=v;
			bt[fr].push_back(x);
			q.push_back(to);
			co[to]=k;
			root[to]=i;
		}
	}while(to!=0);
	return 0;
}
int set(int i)
{
	f[i]=i;return 0;
}
int link(int i,int j)
{
	f[j]=f[i];
	return 0;
}
int find(int x)
{
	int t=f[x];
	if(f[x]!=x)
	{
		f[x]=find(f[x]);
		if(be[t]!=0)
			be[x]=min(be[t],be[x]);
	}
	return f[x];
}
int check()
{
	for(int i=1;i<=n;i++)
	{
		cout<<i<<" "<<f[i]<<endl;
	}
	return 0;
}
int lca(int r)
{
	for(int i=0;i<bt[r].size();i++)
	{
		miku x=bt[r][i];
		lca(x.to);
    }
	set(r);
	for(int i=0;i<bt[r].size();i++)
	{
		link(r,find(bt[r][i].to));
		
		//cout<<bt[r][i].to<<endl;
		if(be[bt[r][i].to]==0)
		be[bt[r][i].to]=bt[r][i].lo;
		else
			be[bt[r][i].to]=min(be[bt[r][i].to],bt[r][i].lo);
	}
	int t=p[r].size();
	while(t>0)
	{
		miku2 w=p[r].front();
		p[r].pop_front();
		if(f[w.wi]!=0)
		{
			miku3 x;
			x.t1=r;x.t2=w.wi;x.num=w.num;
			dark.push_back(x);
		}
		else
			p[r].push_back(w);
			t--;
	}
	//check();
	t=dark.size();
	while(t>0)
	{
		miku3 x=dark.front();
		dark.pop_front();
		//cout<<r<<" "<<x.t1<<" "<<x.t2<<" "<<x.num<<" "<<be[x.t1]<<" "<<be[x.t2]<<endl;
		if(find(x.t1)==find(x.t2))
		{
			//cout<<r<<" "<<x.t1<<" "<<x.t2<<" "<<x.num<<" "<<be[x.t1]<<" "<<be[x.t2]<<endl;
			//check();
			ans[x.num]=min(be[x.t1],be[x.t2]);
		
		if(ans[x.num]==0) ans[x.num]=max(be[x.t1],be[x.t2]);
		}
		else
			dark.push_back(x);
			t--;
	}
	return 0;
}
int bcs()
{
	for(int i=1;i<=n;i++)
	{
		if(co[i]==0)
		{
			cnt++;
			co[i]=cnt;
			dfs(i,cnt);
			root[i]=i;
		}
	}
	return 0;
}
int main()
{
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		miku x;
		x.to=b;x.lo=c;
		in[a].push_back(x);
		x.to=a;
		in[b].push_back(x);
	}
	bcs();
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		if(co[t1]!=co[t2])
			ans[i]=-1;
		else
		{
		miku2 x;
		x.wi=t2;x.num=i;p[t1].push_back(x);
		x.wi=t1;p[t2].push_back(x);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i]==0)
			lca(root[i]);
	}
	//for(int i=1;i<=n;i++)
	//{
	//	cout<<i<<" "<<endl;
	//	for(int j=0;j<bt[i].size();j++)
	//		cout<<bt[i][j].to<<" ";
	//	cout<<endl;
	//}
	//printf("%d",dark.size());
	for(int i=1;i<=q;i++)
	printf("%d\n",ans[i]);
	return 0;
}