记录编号	68161	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]旅行	最终得分	100
用户昵称	hobo.96	是否通过	通过
代码语言	C++	运行时间	1.172 s
提交时间	2013-08-17 12:13:33	内存使用	1.86 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXP 5000
#define MAXN 100000
#define ULL int
using namespace std;

int N,M,MAX,MIN,L,T,S,X,Y,C;
int R,I,J,P[MAXP];
int U[MAXN],V[MAXN],W[MAXN],Q[MAXN],ANS,ANSS,ANST;
double A=1e10;

ULL gcd(ULL m,ULL n)//迭代GCD。
{while (n!=0) {ULL r=n;n=m%n;m=r;}return m;}

int find(int x) {R=x;while(R!=P[R]) R=P[R]; I=x;while (I!=R) {J=P[I];P[I]=R;I=J;} return R;}

void merge(int x,int y){if (x<y) P[y]=x;else P[x]=y;}

bool cmp(const int i,const int j) {return W[i]<W[j];}

int main()
{
freopen("comf.in","r",stdin);
freopen("comf.out","w",stdout);
scanf("%d%d",&N,&M);
for (int i=1;i<=M;i++) scanf("%d%d%d",&U[i],&V[i],&W[i]);
scanf("%d%d",&S,&T);
for (int i=1;i<=M;i++) Q[i]=i;
sort(Q,Q+M+1,cmp);

for (int i=1;i<=M;i++)
    {
    for (int l=1;l<=N;l++) P[l]=l;
    merge(U[Q[i]],V[Q[i]]);
    X=find(S);
    Y=find(T);
    if (X==Y) {A=1;ANSS=1;ANST=1;continue;}
    for (int j=i+1;j<=M;j++)
        {
        X=find(U[Q[j]]);
        Y=find(V[Q[j]]);
        if (X==Y) continue;
        else merge(X,Y);
        X=find(S);
        Y=find(T);
        if (X==Y)
            if ( (double)W[Q[j]]/(double)W[Q[i]] < A)
            {
            A=(double)((double)W[Q[j]]/(double)W[Q[i]]);
            ANSS=W[Q[j]];
            ANST=W[Q[i]];
            }
        }
    }
if (A==1e10) cout<<"IMPOSSIBLE"<<endl;
else
    {
    C=gcd(ANSS,ANST);
    if (C==ANST) {ANS=ANSS/C;cout<<ANS<<endl;}
    else {cout<<(int)floor((ANSS/C)+0.5)<<'/'<<(int)floor((ANST/C)+0.5)<<endl;}
    }
return 0;
}