记录编号	233042	评测结果	AAAAAAAAAA
题目名称	[郑州培训2012] 暴力摩托	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2016-03-03 20:56:48	内存使用	0.47 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct rde
{
	int x,y;
	int speed;
};
rde f[10000];
int p[10000]; 
int x1,y1;
bool cmp(const rde a,const rde b)
{
	return a.speed<b.speed;
}
int find(int x)
{
	if(p[x]==x) return x;
	else return p[x]=find(p[x]);
}
int n,m;
int main()
{
	freopen("motor.in","r",stdin);
	freopen("motor.out","w",stdout);
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
	}
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].speed);
	}
	sort(f+1,f+m+1,cmp);
	int k,j;
	scanf("%d",&k);
	for(int l=1;l<=k;l++)
	{
		scanf("%d%d",&x1,&y1);
		int minn=999999999;
		for(int i=1;i<=m;i++)
		{
			for(int q=1;q<=n;q++)
			{
				p[q]=q;
			}
			for(j=i;j<=m;j++)
			{
				int fx=find(f[j].x);
				int fy=find(f[j].y);
				if(fx!=fy)
				{
					p[fx]=fy;
				}
				if(find(x1)==find(y1)) break;
			}
			if(f[j].speed-f[i].speed>=0) minn=min(minn,f[j].speed-f[i].speed);
		}
		cout<<minn<<endl;
	}
	return 0;
}