bic.pas 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
  1. {用SPFA算法实现}
  2. {$R-,S-,Q-}
  3. Program BOI2002_Bicriterial_routing;
  4. Const
  5. Fin = 'bic.in';
  6. Fou = 'bic.out';
  7. Maxn = 100;
  8. MaxNode = 1280128;
  9. Var
  10. Count: Array[1 .. MaxNode]of Boolean; {记录每个顶点当前是否在队列中}
  11. Sta: Array[1 .. MaxNode]of Longint; {求最短路的辅助队列}
  12. Dis: Array[1 .. MaxNode]of Word; {最短路径估计值}
  13. a, b, d: Array[1 .. Maxn, 1 .. Maxn]of Longint; {用邻接表存图}
  14. c: Array[1 .. Maxn]of Longint; {每个点的出度}
  15. n, s, t: Longint;
  16. Procedure Init; {读入}
  17. Var
  18. i, j, k, x, y, m: Longint;
  19. Begin
  20. Assign(Input, Fin);
  21. Reset(Input);
  22. Read(n, m, s, t);
  23. For k:= 1 to m do
  24. Begin
  25. Read(i, j, x, y);
  26. {将每条边拆成两条有向边}
  27. Inc(c[i]);
  28. a[i, c[i]]:= x;
  29. b[i, c[i]]:= y;
  30. d[i, c[i]]:= j;
  31. Inc(c[j]);
  32. a[j, c[j]]:= x;
  33. b[j, c[j]]:= y;
  34. d[j, c[j]]:= i;
  35. End;
  36. Close(Input);
  37. End;
  38. Procedure Main;
  39. Var
  40. v, w, w1, i, j, k, tmp, head, tail: Longint;
  41. Begin
  42. {最短路估计值处始化}
  43. For i:= 1 to MaxNode do
  44. Dis[i]:= 30000;
  45. {起点进入队列}
  46. head:= 1;
  47. tail:= 1;
  48. Sta[1]:= s;
  49. Dis[s]:= 0;
  50. Count[s]:= True;
  51. {SPFA算法的循环}
  52. Repeat
  53. v:= Sta[head] And 127; {得出当前顶点}
  54. w:= Sta[head] Shr 7; {得出当前的费用}
  55. k:= Dis[Sta[head]]; {得出当前最短路长}
  56. For i:= 1 to c[v] do
  57. Begin
  58. w1:= w + a[v, i];
  59. If (w1 > 10000) then Continue; {比可能的最大值大则舍去}
  60. j:= w1 Shl 7 + d[v, i]; {将顶点加密,以节省空间}
  61. {进行松弛操作}
  62. tmp:= k + b[v, i];
  63. If (tmp < Dis[j]) then
  64. Begin
  65. Dis[j]:= tmp;
  66. If Not Count[j] then {不在队列中则进入队列}
  67. Begin
  68. Count[j]:= True;
  69. Inc(tail);
  70. If (tail > MaxNode) then tail:= 1; {队列循环}
  71. Sta[tail]:= j;
  72. End;
  73. End;
  74. End;
  75. Count[Sta[head]]:= False; {队首元素出队}
  76. If (head = tail) then Break; {队列空则循环结束}
  77. {队列循环}
  78. Inc(head);
  79. If (head > MaxNode) then head:= 1;
  80. Until False;
  81. End;
  82. Procedure Print;
  83. Var
  84. i, j, tot, min: Longint;
  85. Begin
  86. min:= 30000; {最短路长最小值设置最大}
  87. tot:= 0;
  88. For i:= 0 to 10000 do {费用i不断增大}
  89. Begin
  90. j:= i Shl 7 + t;
  91. If (Dis[j] < min) then {当前的最短路长比最短路长最小值小,则方案是双调路径}
  92. Begin
  93. min:= Dis[j]; {更新最短路长最小值}
  94. Inc(tot); {更新双调路径总数}
  95. End;
  96. End;
  97. Assign(Output, Fou);
  98. Rewrite(Output);
  99. Writeln(tot);
  100. Close(Output);
  101. End;
  102. Begin
  103. Init;
  104. Main;
  105. Print;
  106. End.