记录编号	227156	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]旅行	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	2.315 s
提交时间	2016-02-18 15:21:10	内存使用	0.31 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=505;
const int maxm=5010;
int n,m;
int ufs[maxn];
int find(int x){
	if(ufs[x]!=x)ufs[x]=find(ufs[x]);
	return ufs[x];
}
void link(int a,int b){
	ufs[find(a)]=find(b);
}
void init(){
	for(int i = 1;i<=n;++i)ufs[i]=i;
}
struct edge{
	int a,b,v;
}lst[maxm];
bool cmp(const edge &a,const edge &b){
	return a.v<b.v;
}
int gcd(int a,int b){
	while(b%a!=0){
		int tmp=b%a;
		b=a;a=tmp;
	}	
	return a;
}
int main(){
	freopen("comf.in","r",stdin);
	freopen("comf.out","w",stdout);
	scanf("%d %d",&n,&m);
	init();
	for(int i=0;i<m;++i){
		scanf("%d %d %d",&lst[i].a,&lst[i].b,&lst[i].v);
		link(lst[i].a,lst[i].b);
	}
	int s,t;
	scanf("%d %d",&s,&t);
	if(find(s)!=find(t)){
		printf("IMPOSSIBLE\n");
	}
	else{
		double ans=1000000.0;int fenmu,fenzi;
		sort(lst,lst+m,cmp);
		for(int i=0;i<m;++i){
			init();
			for(int j=i;j<m;++j){
				link(lst[j].a,lst[j].b);
				if(find(s)==find(t)){
					if(ans>double(lst[j].v)/double(lst[i].v)){
						ans=double(lst[j].v)/double(lst[i].v);
						fenmu=lst[i].v;
						fenzi=lst[j].v;
					}
					break;
				}
			}
		}
		if(fenzi%fenmu==0)printf("%d",fenzi/fenmu);
		else{
			int tmp=gcd(fenmu,fenzi);
			printf("%d/%d",fenzi/tmp,fenmu/tmp);
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}