传送门

边数只有5000,可以考虑\(O(m^2)\)算法,即把所有边按边权升序排序,然后依次枚举每条边\(i\),从这条边开始依次加边,加到起点和终点在一个连通块为止.这个过程可以用并查集维护.那么以\(i\)这条边为最小边的合法路径,最大值最小的边就是最后加进去的边,这时用这两个边权更新答案即可

可以加一些形如当前比值比答案更差就退出的剪枝

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define db double

#define eps (1e-5)

using namespace std;

const int N=500+10,M=5000+10;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

struct ed

{

  int x,y,z;

  bool operator < (const ed &bb) const {return z<bb.z;}

}e[M];

int n,m,ss,tt,a1,a2,fa[N];

db mi=1e18;

il int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}

il void merg(int x,int y){fa[findf(y)]=findf(x);}

il int ggcd(int a,int b){return b?ggcd(b,a%b):a;}

int main()

{

  n=rd(),m=rd();

  for(int i=1;i<=m;i++) e[i].x=rd(),e[i].y=rd(),e[i].z=rd();

  sort(e+1,e+m+1);

  ss=rd(),tt=rd();

  for(int i=1;i<=m;i++)

    {

      for(int j=1;j<=n;j++) fa[j]=j;

      int w1=e[i].z,w2=e[i].z,x=e[i].x,y=e[i].y;

      merg(x,y);

      for(int j=i+1;j<=m&&findf(ss)!=findf(tt);j++)

        {

          int x=e[j].x,y=e[j].y;

          w2=e[j].z;

          merg(x,y);

        }

      if(findf(ss)!=findf(tt)) break;

      if(mi>(db)w2/(db)w1) mi=(db)w2/(db)w1,a1=w1,a2=w2;

    }

  if(!a1) puts("IMPOSSIBLE");

  else

    {

      int gcd=ggcd(a1,a2);

      a1/=gcd,a2/=gcd;

      a1==1?printf("%d\n",a2):printf("%d/%d\n",a2,a1);

    }

  return 0;

}