给你一个无向图,N(N<=500) 个顶点, M(M<=5000) 条边,每条边有一个权值 Vi(Vi<30000)。给你两个顶点 S 和 T,求一条路径,使得路径上最大边和最小边的比值最小。如果 S 和 T 之间没有路径,输出 "IMPOSSIBLE",否则输出这个比值,如果需要,表示成一个既约分数。 备注: 两个顶点之间可能有多条路径。
第一行包含两个正整数,N 和 M。下来的 M 行每行包含三个正整数:x,y 和 v。表示景点 x 到景点 y 之间有一条双向公路,车辆必须以速度 v 在该公路上行驶。最后一行包含两个正整数 s,t,表示想知道从景点 s 到景点 t 最大最小速度比最小的路径。s 和 t 不可能相同。
1<N<=500,1<=x,y<=N,0<v<30000,0<M<=5000
如果景点 s 到景点 t 没有路径,输出 "IMPOSSIBLE"。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。
- 1 program rrr(input, output);
- 2 const 3 inf = 123456789;
- 4 eps = 1e-8;
- 5
- var 6 u, v, w: array[0..5050] of longint;
- 7 father: array[0..505] of longint;
- 8 n,
- m,
- s,
- t,
- i,
- j,
- c,
- d,
- p,
- q: longint;
- 9 min: double;
- 10 procedure sort(q, h: longint);
- 11
- var 12 i, j, x, t: longint;
- 13 begin 14 i: =q;
- j: =h;
- x: =w[(i + j) >> 1];
- 15 repeat 16
- while w[i] do inc(i);
- 17
- while xdo dec(j);
- 18
- if i <= j then 19 begin 20 t: =u[i];
- u[i] : =u[j];
- u[j] : =t;
- 21 t: =v[i];
- v[i] : =v[j];
- v[j] : =t;
- 22 t: =w[i];
- w[i] : =w[j];
- w[j] : =t;
- 23 inc(i);
- dec(j);
- 24 end;
- 25 until i > j;
- 26
- if j > q then sort(q, j);
- 27
- if ithen sort(i, h);
- 28 end;
- 29
- function find(k: longint) : longint;
- 30 begin 31
- if father[k] = k then exit(k);
- 32 father[k] : =find(father[k]);
- 33 exit(father[k]);
- 34 end;
- 35
- function gcd(a, b: longint) : longint;
- 36
- var 37 r: longint;
- 38 begin 39 r: =a mod b;
- 40
- while r < >0 do begin a: =b;
- b: =r;
- r: =a mod b;
- end;
- 41 exit(b);
- 42 end;
- 43 begin 44 assign(input, 'r. in ');
- assign(output, 'r.out');
- reset(input);
- rewrite(output);
- 45 readln(n, m);
- 46
- for i: =1 to m do readln(u[i], v[i], w[i]);
- 47 readln(s, t);
- 48 sort(1, m);
- 49 min: =inf;
- 50
- for i: =1 to m do 51 begin 52
- for j: =1 to n do father[j] : =j;
- 53
- for j: =i to m do 54 begin 55 c: =find(u[j]);
- d: =find(v[j]);
- 56
- if c < >d then father[c] : =d;
- 57 c: =find(s);
- d: =find(t);
- 58
- if c = d then
- break;
- 59 end;
- 60
- if c = d then
- if w[j] / w[i] then begin min: =w[j] / w[i];
- p: =w[i];
- q: =w[j];
- end;
- 61 end;
- 62
- if abs(min - inf) then write('IMPOSSIBLE') 63
- else begin c: =gcd(p, q);
- p: =p div c;
- q: =q div c;
- if p = 1 then write(q)
- else write(q, ' / ', p);
- end;
- 64 close(input);
- close(output);
- 65 end.
来源: http://www.bubuko.com/infodetail-1967008.html