P 1001 舒适的路线

  1 const maxe=10001; maxn=1000; maxx=1000000; inf=1000000000;
  2 type
  3   node=record
  4     next,t,v:longint;
  5   end;
  6 var n,m,i,j,u,x,y,s,t,num,cnt,xa,xb:longint;
  7 ans:double;
  8 head,dl,du:array[0..maxn] of longint;
  9 f:array[0..maxx] of longint;
 10 h:array[0..maxx] of longint;
 11 b:array[0..maxe] of node;
 12 p:array[0..maxn] of boolean;
 13 v:array[0..maxe] of longint;
 14 function max(a,b:longint):longint;
 15 begin if a>b then exit(a) else exit(b); end;
 16 function min(a,b:longint):longint;
 17 begin if a>b then exit(b) else exit(a); end;
 18 procedure insert(u,x,y:longint);
 19 begin
 20   inc(num);
 21   with b[num] do
 22     begin
 23       next:=head[u];
 24       t:=x;
 25       v:=y;
 26     end;
 27   head[u]:=num;
 28 end;
 29 function hash(x:longint):boolean;
 30 var i:longint;
 31 begin
 32   i:=x;
 33   while (h[i]<>x) and (h[i]<>0) do
 34     begin
 35       inc(i);
 36       i:=i mod maxx;
 37     end;
 38   if h[i]=0 then
 39     begin
 40       h[i]:=x;
 41       exit(true);
 42     end
 43   else exit(false);
 44 end;
 45 procedure spfa(maxv:longint);
 46 var e,v,now,l,r:longint;
 47 begin
 48   fillchar(p,sizeof(p),true);
 49   for l:=1 to n do dl[l]:=inf;
 50   l:=1; r:=1; f[1]:=s; p[s]:=false;
 51   while l<=r do
 52     begin
 53       now:=f[l];
 54       e:=head[now];
 55       while e<>0 do
 56         begin
 57           v:=b[e].t;
 58           if (b[e].v<=maxv) and ((dl[v]=inf) or (dl[v]<min(dl[now],b[e].v))) then
 59             begin
 60               dl[v]:=min(dl[now],b[e].v);
 61               if p[v] then
 62                 begin
 63                   p[v]:=false;
 64                   inc(r);
 65                   f[r]:=v;
 66                 end;
 67             end;
 68           e:=b[e].next;
 69         end;
 70       inc(l);
 71       p[now]:=true;
 72     end;
 73   if dl[t]<>inf then
 74     if ans>maxv/dl[t] then
 75       begin
 76         ans:=maxv/dl[t];
 77         xa:=maxv;
 78         xb:=dl[t];
 79       end;
 80 end;
 81 procedure work;
 82 var i:longint;
 83 begin
 84   for i:=1 to cnt do
 85     spfa(v[i]);
 86 end;
 87 function gcd(a,b:longint):longint;
 88 begin
 89   if a mod b=0 then exit(b);
 90   exit(gcd(b,a mod b));
 91 end;
 92 procedure print;
 93 var tem:longint;
 94 begin
 95   if xa mod xb=0 then writeln(xa div xb)
 96     else begin
 97       tem:=gcd(xa,xb);
 98       writeln(xa div tem,‘/‘,xb div tem);
 99     end;
100 end;
101 begin
102   readln(n,m);
103   for i:=1 to m do
104     begin
105       readln(u,x,y);
106       insert(u,x,y);
107       insert(x,u,y);
108       if hash(y) then
109         begin
110           inc(cnt);
111           v[cnt]:=y;
112         end;
113     end;
114   readln(s,t); ans:=inf;
115   work;
116   if trunc(ans)=inf then writeln(‘IMPOSSIBLE‘)
117     else print;
118 end.