Advertisement
Dennnhhhickk

Untitled

Nov 28th, 2016
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 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: integer;
  15. a: array [1..MAXIN, 1..MAXIN] of integer;
  16. d, d1, ans, mark: array [1..MAXIN] of integer;
  17. min: extended;
  18.  
  19. begin
  20. readln(n, m, e);
  21.  
  22. for i := 1 to MAXIN do
  23. for j := 1 to MAXIN do
  24. a[i][j] := 0;
  25.  
  26. for i := 1 to m do
  27. begin
  28. readln(a1, b1, d[i]);
  29. d1[i] := d[i];
  30. a[a1][b1] := 1;
  31. a[b1][a1] := 1;
  32. mark[i] := 0;
  33. end;
  34.  
  35. for i := 1 to e do
  36. read(ans[i]);
  37.  
  38. readln(p, s);
  39. d[p] := 0;
  40. d1[s] := 0;
  41.  
  42. while (true) do
  43. begin
  44. ind := -1;
  45. min := INF;
  46. for i := 1 to m do
  47. if (mark[i] = 0) and (d[i] < min) then
  48. begin
  49. ind := i;
  50. min := d[i];
  51. end;
  52. if (ind = -1) then
  53. break;
  54. mark[ind] := 1;
  55. for u := 1 to m do
  56. if (a[ind][u] <> -1) and (mark[u] = 0) and (d[u] > d[ind] + a[ind][u]) then
  57. d[u] := d[ind] + a[ind][u];
  58. end;
  59.  
  60. while (true) do
  61. begin
  62. ind := -1;
  63. min := INF;
  64. for i := 1 to m do
  65. if (mark[i] = 0) and (d1[i] < min) then
  66. begin
  67. ind := i;
  68. min := d1[i];
  69. end;
  70. if (ind = -1) then
  71. break;
  72. mark[ind] := 1;
  73. for u := 1 to m do
  74. if (a[ind][u] <> -1) and (mark[u] = 0) and (d1[u] > d1[ind] + a[ind][u]) then
  75. d1[u] := d1[ind] + a[ind][u];
  76. end;
  77.  
  78. min := MAXINT;
  79.  
  80. for i := 1 to e do
  81. if (d[ans[i]] < d1[ans[i]]) then
  82. if ((d[ans[i]] * 160000) / d1[ans[i]] - min < eps) then
  83. min := (d[ans[i]] * 160000) / d1[ans[i]] / 1000;
  84.  
  85. if (min = MAXINT) then
  86. writeln('IMPOSSIBLE')
  87. else
  88. writeln(min:0:7);
  89.  
  90. readln;
  91. readln;
  92. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement