枚举$O(n^2)$,并查集$O(nlog_{n})$水过~

代码题。

# include <stdio.h>
# include <algorithm>
using namespace std;
const int Maxn=510,Maxm=6010;
int ans1=313313111,ans2;
int n,m;
class UnionSet {
	public:
		int fa[Maxn];
		inline void init() {
			for (int i=1;i<=Maxn;++i) fa[i]=i;
		}
		inline int find(int x) {
			return fa[x] == x ? x : fa[x] = find(fa[x]);
		}
		inline bool unioned(int fx,int fy) {
			fa[fx]=fy;
		}
}A;
typedef struct e {
	int u,v,x;
}E;
E a[Maxm];
inline void scan(int i) {
	scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].x);
}
inline bool cmp(E a,E b) {
	return a.x>b.x;
}
inline void stlsort() {
	sort(a+1,a+m+1,cmp);
}
inline void geth(int &u,int &v,int &w,int pos) {
	u=a[pos].u,v=a[pos].v,w=a[pos].x;
}
int s,t;
inline int gcd(int a,int b) {
	int r;
	while(b!=0) {
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}
main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) scan(i);
	stlsort();
	scanf("%d%d",&s,&t);
	if(s==t) {
		printf("1\n");
		return 0;
	}
	for (int i=m;i>=1;--i) {
		int jw;
		A.init();
		for (int j=i;j>=1;--j) {
			int u,v,w;
			geth(u,v,w,j);
			if(j==i) jw=w;	
			int fu=A.find(u),fv=A.find(v);
			if(fu!=fv) {
				A.unioned(fu,fv);
			}
			int fx=A.find(s),fy=A.find(t);
			if(fx==fy) {
				if((double)ans1/ans2>(double)w/jw) {
					int gc=gcd(w,jw);
					ans1=w/gc;
					ans2=jw/gc;
				}
				j=0;
			}
		}
	}
	if(ans1==313313111) {
		printf("IMPOSSIBLE\n");
		return 0;
	}
	if(ans2==1) printf("%d\n",ans1);
	else printf("%d/%d\n",ans1,ans2);
	return 0;
}