Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- program Project2;
- {$APPTYPE CONSOLE}
- uses
- SysUtils;
- const
- INF = MAXINT - 100;
- MAXIN = 10000;
- eps = 1e-7;
- var
- n, m, e, i, j, u, a1, b1, p, s, ind: integer;
- a: array [1..MAXIN, 1..MAXIN] of integer;
- d, d1, ans, mark: array [1..MAXIN] of integer;
- min: extended;
- begin
- readln(n, m, e);
- for i := 1 to MAXIN do
- for j := 1 to MAXIN do
- a[i][j] := 0;
- for i := 1 to m do
- begin
- readln(a1, b1, d[i]);
- d1[i] := d[i];
- a[a1][b1] := 1;
- a[b1][a1] := 1;
- mark[i] := 0;
- end;
- for i := 1 to e do
- read(ans[i]);
- readln(p, s);
- d[p] := 0;
- d1[s] := 0;
- while (true) do
- begin
- ind := -1;
- min := INF;
- for i := 1 to m do
- if (mark[i] = 0) and (d[i] < min) then
- begin
- ind := i;
- min := d[i];
- end;
- if (ind = -1) then
- break;
- mark[ind] := 1;
- for u := 1 to m do
- if (a[ind][u] <> -1) and (mark[u] = 0) and (d[u] > d[ind] + a[ind][u]) then
- d[u] := d[ind] + a[ind][u];
- end;
- while (true) do
- begin
- ind := -1;
- min := INF;
- for i := 1 to m do
- if (mark[i] = 0) and (d1[i] < min) then
- begin
- ind := i;
- min := d1[i];
- end;
- if (ind = -1) then
- break;
- mark[ind] := 1;
- for u := 1 to m do
- if (a[ind][u] <> -1) and (mark[u] = 0) and (d1[u] > d1[ind] + a[ind][u]) then
- d1[u] := d1[ind] + a[ind][u];
- end;
- min := MAXINT;
- for i := 1 to e do
- if (d[ans[i]] < d1[ans[i]]) then
- if ((d[ans[i]] * 160000) / d1[ans[i]] - min < eps) then
- min := (d[ans[i]] * 160000) / d1[ans[i]] / 1000;
- if (min = MAXINT) then
- writeln('IMPOSSIBLE')
- else
- writeln(min:0:7);
- readln;
- readln;
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement