记录编号	114547	评测结果	AAAAAAAAAA
题目名称	[郑州培训2012] 暴力摩托	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.268 s
提交时间	2014-07-31 16:05:40	内存使用	0.20 MiB

#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fin("motor.in");
ofstream fout("motor.out");
const int INF=999999999;
class woca
{
public:
	int f;
	int t;
	int value;
};
woca F[1010];
int father[1010];
int N,M,K;
int MIN=INF;
bool CP(woca a,woca b)
{
	if(a.value<=b.value)
		return 1;
	return 0;
}
int Getfather(int v)
{
	if(father[v]==v)
		return v;
	return father[v]=Getfather(father[v]);
}
int main()
{
	fin>>N>>M;
	int i,j,A,B,k,x,y;
	for(i=1;i<=M;i++)
		fin>>F[i].f>>F[i].t>>F[i].value;
	sort(F+1,F+M+1,CP);
	fin>>K;
	for(k=1;k<=K;k++)
	{
		fin>>x>>y;
		MIN=INF;
	for(i=1;i<=M;i++)//枚举最小边
	{
		for(j=1;j<=N;j++)
			father[j]=j;
		for(j=i;j<=M;j++)
		{
			A=Getfather(F[j].f);
			B=Getfather(F[j].t);
			if(A!=B)
				father[A]=B;
			if(Getfather(x)==Getfather(y))
				break;
		}
		if(F[j].value-F[i].value>=0)
		MIN=min(MIN,F[j].value-F[i].value);
	}
	fout<<MIN<<endl;
	}
	return 0;
}