codevs 舒适的路线 1001

题目描述 Description         Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。 输入描述 Input Description 第一行包含两个正整数，N和M。接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。 输出描述 Output Description 如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。 样例输入 Sample Input 样例1 4 2 1 2 1 3 4 2 1 4

样例2

3 3 1 2 10 1 2 5 2 3 8 1 3 样例3 3 2 1 2 2 2 3 4 1 3 样例输出 Sample Output 样例1 IMPOSSIBLE 样例2 5/4 样例3

2

代码：

    var   flag,s1,t1,s,t,n,m,i,j:longint;   f,v,x,y:array[0..50000]of longint; function gcd(x,y:longint):longint; begin   if x mod y=0 then exit(y);   gcd:=gcd(y,x mod y); end; procedure qsort(l,r:longint); var   i,j,t:longint; begin   i:=l;j:=r;t:=v[random(l+r-1)];   repeat     while v[i]>t do inc(i);     while v[j]<t do dec(j);     if i<=j then begin       x[0]:=x[i];x[i]:=x[j];x[j]:=x[0];       y[0]:=y[i];y[i]:=y[j];y[j]:=y[0];       v[0]:=v[i];v[i]:=v[j];v[j]:=v[0];       inc(i);dec(j);     end;   until i>j;   if l<j then qsort(l,j);   if i<r then qsort(i,r); end; function father(x:longint):longint; begin   if f[x]=x then exit(x);   f[x]:=father(f[x]);   exit(f[x]); end; procedure main(xx:longint); var   i,j,k:longint; begin   for i:=1 to n do     f[i]:=i;   for i:=xx to m do     begin       f[father(x[i])]:=father(y[i]);       if father(s)=father(t)         then begin                inc(flag);                if flag=1 then begin                                 s1:=v[xx];                                 t1:=v[i];                               end;                if (v[xx]/v[i])<(s1/t1)                  then begin                         t1:=v[i];                         s1:=v[xx];                       end;              end;     end; end; begin   readln(n,m);   for i:=1 to m do     readln(x[i],y[i],v[i]);   qsort(1,m);   readln(s,t);   for i:=1 to m do     main(i);   if flag=0 then writeln('IMPOSSIBLE')     else if s1 mod t1=0 then writeln(s1 div t1)            else writeln(s1 div gcd(s1,t1),'/',t1 div gcd(s1,t1)); end.