BSOI_2016.旅行(comf.pas/c/cpp)

【問題の説明】Z町は景色のいい場所で、各地からの観光客を誘致して観光しています.Z町の近くにはNの観光地(番号1,2,3,...,N)があり、これらの観光地はMの道路でつながっており、すべての道路が双方向で、2つの観光地の間に複数の道路がある可能性があります.この地の観光資源を守るためかもしれないが、Z町には奇妙な規定がある.与えられた道路Riに対して、この道路を走る車の速度はViでなければならない.スピードの変化が速すぎて観光客が気分が悪いので、一つの観光地から別の観光地に行くときは、最大速度と最小速度のできるだけ小さいルート、いわゆる最も快適なルートを選びたいと思っています.【入力ファイル】1行目は、2つの正の整数、NおよびMを含む.次のM行の各行は、x,y,vの3つの正の整数を含む.観光地xから観光地yまでの間に双方向道路があり、車両は速度vでこの道路を走行しなければならないことを示す.最後の行には、2つの正の整数s,tが含まれており、観光地sから観光地tまでの最大最小速度比が最小である経路を知りたいことを示している.sとtが同じであるはずがない.【出力ファイル】スポットsからスポットtへの経路がない場合は、「IMPOSIBLE」を出力する.そうでなければ、最小の速度比を表す数を出力します.必要に応じて、既約スコアを出力します.【サンプル入出力】【サンプル入力1】4 2 1 2 1 3 4 1 4【サンプル入力2】3 3 1 2 10 1 2 5 3 8 1【サンプル入力3】3 2 1 2 2 2 3 3【サンプル出力1】IMPOSIBLE【サンプル出力2】5/4【サンプル出力3】2【データ範囲】100%のデータに対して1

#include
#include
#define N 501
#define M 5001
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
    int x,y,v;
    bool operatorreturn vint n,m,s,t,minn=1,maxx=INF,f[N];
int find(int x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
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",&e[i].x,&e[i].y,&e[i].v);
    scanf("%d%d",&s,&t);
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        int j;
        for(j=1;j<=n;j++) f[j]=j;
        for(j=i;j<=m;j++)
        {
            int xx=find(e[j].x),yy=find(e[j].y);
            if(xx!=yy) f[yy]=xx;
            if(f[find(s)]==f[find(t)]) break;
        }
        if(j>m) break;
        if(e[j].v*minn*maxx) minn=e[i].v,maxx=e[j].v;
    }
    int g=gcd(maxx,minn);
    maxx/=g,minn/=g;
    if(maxx==INF) printf("IMPOSSIBLE");
    else if(minn==1) printf("%d",maxx);
         else printf("%d/%d",maxx,minn);
    fclose(stdin);
    fclose(stdout);
    return 0;
}