find the most comfortable road
Problem Description
XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure—超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。
Input
输入包括多个测试实例，每个实例包括：
第一行有2个正整数n(1< n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q（Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。
Output
每个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。
Sample Input
4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2
Sample Output
1
0
思路：
比较经典的并查集维护相连的点，判断点与点之间的关系，枚举每组数据所用的最小的边-最大的边,需要排序。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010;
int n,m,tot,father[maxn];
struct node
{
int x;
int y;
int w;
bool operator < (node tmp)const
{
return w<tmp.w;
}
}e[maxn];
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
int main()
{
int u,v;
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
sort(e+1,e+m+1);
scanf("%d",&tot);
while(tot--)
{
int ans=0x7fffffff;
scanf("%d%d",&u,&v);
for(int k=1;k<=m;k++)//枚举下界
{
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=k;i<=m;i++)//枚举上界
{
int f1=find(e[i].x);
int f2=find(e[i].y);
if(f1!=f2) father[f2]=f1;
if(find(u)==find(v))
{
ans=min(ans,e[i].w-e[k].w);
break;
}
}
}
if(ans==0x7fffffff) printf("-1
");
else printf("%d
",ans);
}
}
return 0;
}