今天复习了并查集！
首先对输入的速度
进行结构体排序。
不断地合并路径直到起点与终点相连。
算出最大最小速度比并不断更新最小。
最后分三种情况输出。
具体看：
代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int h[100010],fa[100010];
double minn=2147483647;
int n,m,s,t,ss,tt;
int tot;
struct node
{int x,y,v;
}a[1000010];
bool cmp(const node&a,const node&b)
{return a.v<b.v;
}
int find(int x)
{if(fa[x]==x)return fa[x];return fa[x]=find(fa[x]);
}
int main()
{cin>>n>>m;for(int i=1; i<=m; i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);cin>>s>>t;sort(a+1,a+1+m,cmp);for(int i=1; i<=m; i++){for(int j=1; j<=n; j++)fa[j]=j;int k=i,w=0;while(k<=m){fa[find(a[k].x)]=find(a[k].y); //合并if(find(s)==find(t)) //判断起终点是否属于同一个集合{w=1;break;}k++;}if(w==1){if(a[k].v*1.0/a[i].v*1.0<minn) //比较得最小{minn=a[k].v*1.0/a[i].v*1.0;ss=a[i].v;tt=a[k].v;}}}if(minn==2147483647) //三种情况，不解释cout<<"IMPOSSIBLE";else if(ss%tt==0)cout<<ss/tt;elsecout<<tt/__gcd(tt,ss)<<"/"<<ss/__gcd(tt,ss);return 0;
}