传送门 spfa有反例(自己yy) 我们可以暴力枚举最短边，然后做kruscal。 这样时间复杂度是O（M^2）的
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node{ int x,y,v; }a[5005]; int fa[505]; int n,m,u,v,ansx,ansy,s,t; bool cmp(node a,node b){ return a.v<b.v; } int getf(int x){ return fa[x]==x?x:fa[x]=getf(fa[x]); } int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); scanf("%d%d",&s,&t); sort(a+1,a+m+1,cmp); ansx=50000; ansy=1; for (int i=1;i<=m;i++) if (a[i].v!=a[i-1].v){ for (int j=1;j<=n;j++) fa[j]=j; for (int j=i;j<=m;j++){ u=getf(a[j].x); v=getf(a[j].y); if (u!=v){ fa[u]=v; if (getf(s)==getf(t)){ u=gcd(a[i].v,a[j].v); v=a[j].v/u; u=a[i].v/u; if (v*ansy<u*ansx){ ansx=v; ansy=u; } break; } } } } if (ansx/ansy>40000) printf("IMPOSSIBLE"); else if (ansx%ansy==0) printf("%d",ansx/ansy); else printf("%d/%d",ansx,ansy); return 0; }