临行前最后一题，居然还不给我1A.题意，给出一堆B-A<=C,问1和N这两人的最大差值。 直接差分约束求最短路，即最大值即可。 初值将1设为0,那么最大差值就是dis[n],AC. 但是这道题居然卡SPFA,太神奇了。 然后要DIJ+HEAP才可以。 看了DISCUSS说，SPFA把队列改成栈就能过，真是神奇。
01.#include <set>
02.#include <map>
03.#include <stack>
04.#include <cmath>
05.#include <queue>
06.#include <cstdio>
07.#include <string>
08.#include <vector>
09.#include <iomanip>
10.#include <cstring>
11.#include <iostream>
12.#include <algorithm>
13.#define Max 2505
14.#define FI first
15.#define SE second
16.#define ll long long
17.#define PI acos（-1.0）
18.#define inf 0x3fffffff
19.#define LL（x） （ x 《 1 ）
20.#define bug puts（"here"）
21.#define PII pair<int,int>
22.#define RR（x） （ x 《 1 | 1 ）
23.#define mp（a,b） make_pair（a,b）
24.#define mem（a,b） memset（a,b,sizeof（a））
25.#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
26.
27.using namespace std;
28.
29.#define M 999999
30.#define N 111111
31.int n , m ;
32.struct kdq {
33. int e , l , next ;
34.} ed[M] ;
35.int head[N] , num ;
36.void init（） {
37. mem（head ,-1） ;
38. num = 0 ;
39.}
40.void add（int s ,int e ,int l） {
41. ed[num].e = e ;
42. ed[num].l = l ;
43. ed[num].next = head[s] ;
44. head[s] = num ++ ;
45.}
46.int dis[N] , cnt[N] ;
47.bool vis[N] ;
48.queue<int>qe ;
49.int spfa（） {
50. while（！qe.empty（））qe.pop（） ;
51. for （int i = 0 ; i <= n ; i ++ ）dis[i] = inf ,cnt[i] = 0 ;
52. dis = 0 ;
53. mem（vis ,0） ;
54. qe.push（1） ;
55. vis = 1 ;
56. while（！qe.empty（）） {
57. int tp = qe.front（） ;
58. qe.pop（） ;
59. vis[tp] = 0 ;
60. if（cnt[tp] > n）return -1 ;
61. for （int i = head[tp] ; ~i ; i = ed[i].next ） {
62. int e = ed[i].e ;
63. int l = ed[i].l ;
64. if（dis[e] > dis[tp] + l） {
65. dis[e] = dis[tp] + l ;
66. if（！vis[e]） {
67. vis[e] = 1 ;
68. qe.push（e） ;
69. cnt[e] ++ ;
70. }
71. }
72. }
73. }
74. return dis[n] - dis ;
75.}
76.
77.struct DIJ {
78. int e , l ;
79. DIJ（） {}
80. DIJ（int ee , int lx）：e（ee） , l（lx） {}
81. bool operator < （const DIJ &fk ）const {
82. return l > fk.l ;
83. }
84.} ;
85.//queue<DIJ>q ;
86.int dij（） {
87. priority_queue<DIJ>q ;
88. for （int i = 1 ; i <= n ; i ++ ）dis[i] = inf ;
89. mem（vis ,0） ;
90. dis = 0 ;
91. q.push（（DIJ） {
92. 1 , 0
93. }） ;
94. while（！q.empty（）） {
95. DIJ tp = q.top（） ;
96. q.pop（） ;
97. if（vis[tp.e]）continue ;
98. vis[tp.e] = 1 ;
99. for （int i = head[tp.e] ; ~i ; i = ed[i].next ） {
100. int e = ed[i].e ;
101. int l = ed[i].l ;
102. if（dis[e] > dis[tp.e] + l ） {
103. dis[e] = dis[tp.e] + l ;
104. q.push（DIJ（e , dis[e]）） ;
105. }
106. }
107. }
108. return dis[n] ;
109.}
110.int main（） {
111. while（cin 》 n 》 m ） {
112. int a , b , c ;
113. init（） ;
114. for （int i = 0 ; i < m ; i ++ ） {
115. scanf（"%d%d%d",&a,&b,&c） ;
116. add（a , b , c） ;
117. }
118. printf（"%d\n",dij（）） ;
119. }
120. return 0 ;
121.} |