Advertisement
Dennnhhhickk

Untitled

Nov 29th, 2016
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.68 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 (mark[i] = 0) and (bory[i] < min1) then
  73. begin
  74. ind := i;
  75. min1 := bory[i];
  76. end;
  77. if (ind = -1) then
  78. break;
  79. mark[ind] := 1;
  80. for i := 1 to n do
  81. if (a[ind][i] <> -1) and (mark[i] = 0) and (bory[i] > bory[ind] + a[ind][i]) then
  82. bory[i] := bory[ind] + a[ind][i];
  83. end;
  84.  
  85. while (true) do
  86. begin
  87. ind := -1;
  88. min1 := INF;
  89. for i := 1 to n do
  90. if (i <> p) then
  91. if (mark1[i] = 0) and (pasha[i] < min1) then
  92. begin
  93. ind := i;
  94. min1 := pasha[i];
  95. end;
  96. if (ind = -1) then
  97. break;
  98. mark1[ind] := 1;
  99. for i := 1 to n do
  100. if (i <> p) then
  101. if (a[ind][i] <> -1) and (mark1[i] = 0) and (pasha[i] > pasha[ind] + a[ind][i]) then
  102. pasha[i] := pasha[ind] + a[ind][i];
  103. end;
  104.  
  105. {for i := 1 to n do
  106. begin
  107. if (bory[i] = INF) then
  108. bory[i] := 0;
  109. if (pasha[i] = INF) then
  110. pasha[i] := 0;
  111. end; }
  112.  
  113. minspeed[s] := 0;
  114.  
  115. while (true) do
  116. begin
  117. ind := -1;
  118. min12 := INF;
  119. for i := 1 to n do
  120. if (minspeed[i] < min12) and (mark12[i] = 0) then
  121. begin
  122. ind := i;
  123. min12 := minspeed[i];
  124. end;
  125. if (ind = -1) then
  126. break;
  127. mark12[ind] := 1;
  128. for i := 1 to n do
  129. if (i <> ind) and (bory[i] <> 0) and (bory[i] <> INF) and (pasha[i] <> INF) then
  130. minspeed[i] := min(minspeed[i], max(minspeed[ind], 160 * pasha[i]/bory[i]));
  131. end;
  132.  
  133. for i := 1 to n do
  134. writeln(minspeed[i]:0:7);
  135.  
  136. readln;
  137. readln;
  138. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement