n次最小生成树kruskal
将所有的边排序，权值小的在前。
设排序后第i条边为路径中的最长边，那么这条路径一定是由1~i中的一些边组成
因为最高速和最低速的差尽量小，最高速确定了，最低速应尽量大。
所以j从i downto 1，将边j加入边集，如果此时s和t联通了（s t在并查集的一个集合中），那么找到一组可行的解：最大i.w，最小j.w，与最优解比较、更新。
如果还没联通，继续找下一个j。直到j到1还没有，那么说明i为最大边是不行的，i++继续。
代码：
#include<iostream>
#include<algorithm>
#define MaxN 505
#define MaxM 5005
using namespace std; int n,m;
struct edge{
int u,v,w;
}eg[MaxM];
bool flag=false;
int ansa=0x3f3f3f3f,ansb=;
int start,end; int pa[MaxN];
void init(){
for(int i=;i<=n;i++)pa[i]=i;
}
int find(int x){
if(x!=pa[x])pa[x]=find(pa[x]);
return pa[x];
}
void un(int x,int y){
if(find(x)==find(y))return;
pa[find(x)]=find(y);
} bool ff(edge a,edge b){
return a.w<b.w;
}
int gcd(int a,int b){
return b?gcd(b,a%b):a;
} void out(int a,int b){
if((double)a/b < (double)ansa/ansb){
int t=gcd(a,b);
ansa=a/t;
ansb=b/t;
//cout<<a<<"/"<<b<<" "<<ansa<<"/"<<ansb<<endl;
}
} int main(){
cin>>n>>m;
for(int i=;i<=m;i++){
scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);
}
cin>>start>>end; sort(eg+,eg++m,ff); for(int i=;i<=m;i++){
init();
for(int j=i;j>=;j--){
un(eg[j].u,eg[j].v);
if(find(start)==find(end)){
out(eg[i].w,eg[j].w);
flag=true;
}
}
}
if(flag){
cout<<ansa;
if(ansb!=)cout<<'/'<<ansb;
}
else cout<<"IMPOSSIBLE";
return ;
}