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, min1, d2: integer;
- a: array [1..MAXIN, 1..MAXIN] of integer;
- bory, pasha, ans, mark, mark1, mark12: array [1..MAXIN] of integer;
- Bspd, minspeed: array [1..MAXIN] of extended;
- min12: extended;
- function min(a, b: extended): extended;
- begin
- if (a < b) then
- min := a
- else
- min := b;
- end;
- function max(a, b: extended): extended;
- begin
- if (a > b) then
- max := a
- else
- max := b;
- end;
- begin
- readln(n, m, e);
- for i := 1 to MAXIN do
- for j := 1 to MAXIN do
- a[i][j] := -1;
- for i := 1 to m do
- begin
- readln(a1, b1, d2);
- a[a1][b1] := d2;
- a[b1][a1] := d2;
- end;
- for i := 1 to n do
- begin
- bory[i] := INF;
- pasha[i] := inf;
- mark[i] := 0;
- mark1[i] := 0;
- mark12[i] := 0;
- minspeed[i] := INF;
- end;
- for i := 1 to e do
- read(ans[i]);
- readln(p, s);
- bory[p] := 0;
- pasha[s] := 0;
- while (true) do
- begin
- ind := -1;
- min1 := INF;
- for i := 1 to n do
- if (i <> s) then
- if (mark[i] = 0) and (bory[i] < min1) then
- begin
- ind := i;
- min1 := bory[i];
- end;
- if (ind = -1) then
- break;
- mark[ind] := 1;
- for i := 1 to n do
- if (i <> s) then
- if (a[ind][i] <> -1) and (mark[i] = 0) and (bory[i] > bory[ind] + a[ind][i]) then
- bory[i] := bory[ind] + a[ind][i];
- end;
- while (true) do
- begin
- ind := -1;
- min1 := INF;
- for i := 1 to n do
- //if (i <> p) then
- if (mark1[i] = 0) and (pasha[i] < min1) then
- begin
- ind := i;
- min1 := pasha[i];
- end;
- if (ind = -1) then
- break;
- mark1[ind] := 1;
- for i := 1 to n do
- //if (i <> p) then
- if (a[ind][i] <> -1) and (mark1[i] = 0) and (pasha[i] > pasha[ind] + a[ind][i]) then
- pasha[i] := pasha[ind] + a[ind][i];
- end;
- {for i := 1 to n do
- begin
- if (bory[i] = INF) then
- bory[i] := 0;
- if (pasha[i] = INF) then
- pasha[i] := 0;
- end; }
- minspeed[s] := 0;
- while (true) do
- begin
- ind := -1;
- min12 := INF;
- for i := 1 to n do
- if (minspeed[i] < min12) and (mark12[i] = 0) then
- begin
- ind := i;
- min12 := minspeed[i];
- end;
- if (ind = -1) then
- break;
- mark12[ind] := 1;
- for i := 1 to n do
- if (i <> ind) and (bory[i] <> 0) and (bory[i] <> INF) and (pasha[i] <> INF) then
- minspeed[i] := min(minspeed[i], max(minspeed[ind], 160 * pasha[i]/bory[i]));
- end;
- for i := 1 to n do
- writeln(minspeed[i]:0:7);
- readln;
- readln;
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement