hdu 1598 find the most comfortable road （並查集）

思路：先對所有的邊按z排序，然後依次的枚舉，期間用並查集不斷的合並，

與判斷起點（start）和終點（end）能否聯通，若能則和當前的ans比較大小；
最後若ans==inf，則說明start，end不能形成通路。

********************************************************************************************************************************************

#include<algorithm>

using namespace std;


#define inf 99999999
struct node
{
int x,y;
int z;
}a[5000];


int pre[5000];
int find(int k)
{
if(k==pre[k])
return k;
return pre[k]=find(pre[k]);
}


int cmp(node a,node b)
{
return a.z<b.z;
}


int main()
{
int n,m,t,start,end,f1,f2,ans,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a,a+m,cmp);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&start,&end);
ans=inf;
for(i=0;i<m;i++)
{
for(j=1;j<=n;j++)
pre[j]=j;
for(j=i;j<m;j++)
{
f1=find(a[j].x);
f2=find(a[j].y);
if(f1!=f2)
pre[f1]=f2;
f1=find(start);
f2=find(end);
if(f1==f2)
break;
}
if(j>=m)
break;
if(a[j].z-a[i].z<ans)
ans=a[j].z-a[i].z;
}
if(ans==inf)
printf("-1\n");
else
printf("%d\n",ans);
}
}
return 0;
}