SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
vector<pii> G[maxn];
bool inq[maxn];
int cnt[maxn]; // 记录入队次数
int d[maxn];

inline void init(int n){
for(int i=0;i<=n;i++) G[i].clear();
}
inline void addedge(int u,int v,int w){
G[u].pb(mp(v,w));
// G[v].pb(mp(u,w));
}
bool spfa(int s,int n){
for(int i=0;i<=n;i++) {
d[i] = INF;
inq[i] = 0;
cnt[i] = 0;
}
d[s] = 0;
queue<int> q;
q.push(s);
inq[s] = true;
cnt[s]++;
while(!q.empty()){
int u = q.front();
q.pop();
inq[u] = false;
for(auto V : G[u]){
int v = V.first;
int w = V.second;
if(d[v] > d[u] + w){ // 求最长路的话改成 <
d[v] = d[u] + w;
if(!inq[v]){
inq[v] = true;
cnt[v]++;
q.push(v);
if(cnt[v] >= n) return false;
}
}
}
}
return true;
}