Advertisement
Dennnhhhickk

Untitled

Nov 29th, 2016
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.73 KB | None | 0 0
  1. program Project2;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6. SysUtils;
  7.  
  8. const
  9. INF = MAXINT - 100;
  10. MAXIN = 10000;
  11. eps = 1e-7;
  12.  
  13. var
  14. n, m, e, i, j, u, a1, b1, p, s, ind, min1, d2: integer;
  15. a: array [1..MAXIN, 1..MAXIN] of integer;
  16. bory, pasha, ans, mark, mark1, mark12: array [1..MAXIN] of integer;
  17. Bspd, minspeed: array [1..MAXIN] of extended;
  18. min12: extended;
  19.  
  20. function min(a, b: extended): extended;
  21. begin
  22. if (a < b) then
  23. min := a
  24. else
  25. min := b;
  26. end;
  27.  
  28. function max(a, b: extended): extended;
  29. begin
  30. if (a > b) then
  31. max := a
  32. else
  33. max := b;
  34. end;
  35.  
  36. begin
  37. readln(n, m, e);
  38.  
  39. for i := 1 to MAXIN do
  40. for j := 1 to MAXIN do
  41. a[i][j] := -1;
  42.  
  43. for i := 1 to m do
  44. begin
  45. readln(a1, b1, d2);
  46. a[a1][b1] := d2;
  47. a[b1][a1] := d2;
  48. end;
  49.  
  50. for i := 1 to n do
  51. begin
  52. bory[i] := INF;
  53. pasha[i] := inf;
  54. mark[i] := 0;
  55. mark1[i] := 0;
  56. mark12[i] := 0;
  57. minspeed[i] := INF;
  58. end;
  59.  
  60. for i := 1 to e do
  61. read(ans[i]);
  62.  
  63. readln(p, s);
  64. bory[p] := 0;
  65. pasha[s] := 0;
  66.  
  67. while (true) do
  68. begin
  69. ind := -1;
  70. min1 := INF;
  71. for i := 1 to n do
  72. if (i <> s) then
  73. if (mark[i] = 0) and (bory[i] < min1) then
  74. begin
  75. ind := i;
  76. min1 := bory[i];
  77. end;
  78. if (ind = -1) then
  79. break;
  80. mark[ind] := 1;
  81. for i := 1 to n do
  82. if (i <> s) then
  83. if (a[ind][i] <> -1) and (mark[i] = 0) and (bory[i] > bory[ind] + a[ind][i]) then
  84. bory[i] := bory[ind] + a[ind][i];
  85. end;
  86.  
  87. while (true) do
  88. begin
  89. ind := -1;
  90. min1 := INF;
  91. for i := 1 to n do
  92. //if (i <> p) then
  93. if (mark1[i] = 0) and (pasha[i] < min1) then
  94. begin
  95. ind := i;
  96. min1 := pasha[i];
  97. end;
  98. if (ind = -1) then
  99. break;
  100. mark1[ind] := 1;
  101. for i := 1 to n do
  102. //if (i <> p) then
  103. if (a[ind][i] <> -1) and (mark1[i] = 0) and (pasha[i] > pasha[ind] + a[ind][i]) then
  104. pasha[i] := pasha[ind] + a[ind][i];
  105. end;
  106.  
  107. {for i := 1 to n do
  108. begin
  109. if (bory[i] = INF) then
  110. bory[i] := 0;
  111. if (pasha[i] = INF) then
  112. pasha[i] := 0;
  113. end; }
  114.  
  115. minspeed[s] := 0;
  116.  
  117. while (true) do
  118. begin
  119. ind := -1;
  120. min12 := INF;
  121. for i := 1 to n do
  122. if (minspeed[i] < min12) and (mark12[i] = 0) then
  123. begin
  124. ind := i;
  125. min12 := minspeed[i];
  126. end;
  127. if (ind = -1) then
  128. break;
  129. mark12[ind] := 1;
  130. for i := 1 to n do
  131. if (i <> ind) and (bory[i] <> 0) and (bory[i] <> INF) and (pasha[i] <> INF) then
  132. minspeed[i] := min(minspeed[i], max(minspeed[ind], 160 * pasha[i]/bory[i]));
  133. end;
  134.  
  135. for i := 1 to n do
  136. writeln(minspeed[i]:0:7);
  137.  
  138. readln;
  139. readln;
  140. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement