1
0

layout.pas 2.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  1. Program Usaco_Dec05_layout;
  2. Const
  3. Fin = 'layout.in';
  4. Fou = 'layout.out';
  5. MaxW = 1100000000; {充分大的费用}
  6. Maxn = 1000;
  7. Maxm = 22000;
  8. Var
  9. Dist: Array[1 .. Maxn]of Longint; {最短路长估计值}
  10. a, b, d: Array[1 .. Maxm]of Longint; {单独记录每条边}
  11. n, m, ML, MD: Longint;
  12. Procedure Init;
  13. Var
  14. l, i, j, k: Longint;
  15. Begin
  16. Assign(Input, Fin);
  17. Reset(Input);
  18. Read(n, ML, MD);
  19. m:= 0;
  20. {为满足在队列中顺序与顶点顺序相同而加入的边}
  21. For l:= 2 to n do
  22. Begin
  23. Inc(m);
  24. a[m]:= l;
  25. b[m]:= l - 1;
  26. d[m]:= 0;
  27. End;
  28. {转换存有好感的边}
  29. For l:= 1 to ML do
  30. Begin
  31. Read(i, j);
  32. If i > j then
  33. Begin
  34. k:= i;
  35. i:= j;
  36. j:= k;
  37. End;
  38. Read(k);
  39. Inc(m);
  40. a[m]:= i;
  41. b[m]:= j;
  42. d[m]:= k;
  43. End;
  44. {转换存有反感的边}
  45. For l:= 1 to MD do
  46. Begin
  47. Read(i, j);
  48. If i > j then
  49. Begin
  50. k:= i;
  51. i:= j;
  52. j:= k;
  53. End;
  54. Read(k);
  55. Inc(m);
  56. a[m]:= j;
  57. b[m]:= i;
  58. d[m]:= -k;
  59. End;
  60. Close(Input);
  61. End;
  62. Procedure Main;
  63. Var
  64. i, tmp, tot: Longint;
  65. Quit: Boolean;
  66. Begin
  67. For i:= 2 to n do Dist[i]:= MaxW; {将顶点的最短路设为充分大}
  68. Dist[1]:= 0;
  69. tot:= 0;
  70. {用Bellman-Ford求最短路,并判断是否存在负权圈}
  71. Repeat
  72. Inc(tot); {更新已经对每条边进行松弛操作的次数}
  73. Quit:= True;
  74. For i:= 1 to m do
  75. Begin
  76. tmp:= Dist[a[i]] + d[i];
  77. If tmp < Dist[b[i]] then
  78. Begin
  79. Dist[b[i]]:= tmp;
  80. Quit:= False; {有顶点的最短路径估计值更新了}
  81. End;
  82. End;
  83. Until Quit Or (tot > n); {没有顶点可以更新最短路估计值或存在负权圈}
  84. Assign(Output, Fou);
  85. Rewrite(Output);
  86. If (tot > n) then Writeln(-1) {存在负权圈,满足要求的方案不存在}
  87. Else
  88. If (Dist[n] = MaxW) then Writeln(-2) {当前最短路为充分大,说明距离可以任意大}
  89. Else
  90. Writeln(Dist[n] - Dist[1]); {输出可能的最大距离}
  91. Close(Output);
  92. End;
  93. Begin
  94. Init;
  95. Main;
  96. End.