记录编号	471445	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	snake	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2017-11-06 14:38:57	内存使用	2.69 MiB

//#include<iostream>
#include<cstring>
#include<climits>
#include<ctime>
#include<fstream>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream cin("truck.in");ofstream cout("truck.out");

const int MAX=10010,MAX2=20;
vector<int> map[MAX];	//map[i] 由点i连接出去的所有'边' 
struct edge
{
	int dis;
	int x;
	int y;
	
	bool operator < (const edge& b)const
	{
		return this->dis>b.dis;
	}
};

struct edge2
{
	int dis;
	int target;
};

edge e[MAX*5];	//边 
edge2 f[MAX];	//生成树
edge2 minn[MAX][MAX2];	//minn[i][j]:从i点开始向上2^j个点所经过的边中最小的许可载重(也就是最大可行载重) 
int d[MAX];
bool visited[MAX];
//bool built[MAX];	//built[i]表示并查集祖先为i的集合是否完成了树的构建 (似乎用不着) 

inline int freelog(int n,int a){return int(log2(n)/log2(a));}

//并查集部分↓

int fa[MAX];	//并查集祖先 

void initialization(int n)
{
	for(int i=1;i<=n;i++) fa[i]=i;
	return;
}

int find(int a)
{
	if(fa[a]!=a) fa[a]=find(fa[a]);
	return fa[a];
}

void join(int a,int b)
{
	int aa=find(a);
	int bb=find(b);
	if(aa!=bb) fa[aa]=bb;
	return;
}

bool found(int a,int b)	//return true if a and b had been connected
{
	return find(a)==find(b);
}

//↑并查集部分	树构造函数↓

void create(int t,int de)
{
	d[t]=de;
	visited[t]=1;	//已访问过 
	for(unsigned int i=0;i<map[t].size();i++)
	{
		if((e[map[t][i]].x==t && e[map[t][i]].y==f[t].target) || (e[map[t][i]].x==f[t].target && e[map[t][i]].y==t)) continue;
		int temp=(e[map[t][i]].x==t?e[map[t][i]].y:e[map[t][i]].x);
		f[temp].target=t;
		f[temp].dis=e[map[t][i]].dis;
		create(temp,de+1);
	}
	return;
}

//↑树构造函数	 问题求解↓

int answer(int x,int y)
{
	if(!found(x,y)) return -1;	//no answer
	if(d[x]<d[y]) swap(x,y);
	
	int minx=INT_MAX,miny=INT_MAX;
	
	while(d[x]>d[y])
	{
		int c=freelog(d[x]-d[y],2);
		minx=min(minx,minn[x][c].dis);
		x=minn[x][c].target;
	}
	if(x==y) return minx;
	
	for(int i=freelog(d[x],2);i>=0;i--)
	{
		if(minn[x][i].target!=minn[y][i].target && minn[x][i].target!=0 && minn[y][i].target!=0)
		{
			minx=min(minx,minn[x][i].dis);
			miny=min(miny,minn[y][i].dis);
			
			x=minn[x][i].target;
			y=minn[y][i].target;
		}
	}
	
	minx=min(minx,minn[x][0].dis);
	miny=min(miny,minn[y][0].dis);
	
	return min(minx,miny);
}

//↑问题求解 

int main()
{
	//输入部分↓(checked)
	
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>e[i].x>>e[i].y>>e[i].dis;
	
	//↑输入部分(checked) 最大生成树↓(checked)
	
	initialization(n);
	sort(e+1,e+m+1);
	 int maxx=INT_MIN,maxp;
	for(int i=1;i<=m;i++)
	{
		if(!found(e[i].x,e[i].y))
		{
			int x=e[i].x,y=e[i].y;
			join(x,y);
			map[x].push_back(i);
			map[y].push_back(i);
			if(map[x].size()>=map[y].size() && int(map[x].size())>maxx)
			{
				maxx=map[x].size();
				maxp=x;
			}else if(int(map[y].size())>maxx){
				maxx=map[y].size();
				maxp=y;
			}
		}
	}
	
	//↑最大生成树(checked)	构造树↓(checked) 
	
	f[maxp].target=0;
	f[maxp].dis=0;
	//built[find(maxp)]=1;
	create(maxp,1);
	for(int i=1;i<=n;i++)
	{
		if(!visited[i])
		{
			f[i].dis=0;
			f[i].target=0;
			//built[find(i)]=1;
			create(i,1);
		}
	}
	
	//↑构造树(checked)	路径倍增↓
	
	for(int i=1;i<=n;i++)
	{
		minn[i][0].dis=f[i].dis;
		minn[i][0].target=f[i].target;
	}
	
	for(int j=1;j<MAX2;j++) for(int i=1;i<=n;i++)
	{
		if(minn[i][j-1].target!=-1)
		{
			minn[i][j].dis=min(minn[i][j-1].dis,minn[minn[i][j-1].target][j-1].dis);
			minn[i][j].target=minn[minn[i][j-1].target][j-1].target;
		}
	}
	
	/***********************************************************-*测试*-***********************************************************
	*cout<<endl;
	*for(int i=1;i<=n;i++)
	*{
	*	cout<<i<<endl;
	*	for(int j=0;j<MAX2;j++) cout<<j<<" "<<minn[i][j].target<<" "<<minn[i][j].dis<<endl;
	*	cout<<endl<<endl;
	*}
	*cout<<endl;
	************************************************************-*测试*-************************************************************/
	
	//↑路径倍增	问题求解(逻辑)↓ 
	
	int q;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		cout<<answer(x,y)<<endl;
	}
	
	//↑问题求解(逻辑)
	
	return 0;
}

/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
*/