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
| #define INF 0x3ffffff
#define SPFA_MAX 10010
struct node {
int v, w;
node() { }
node(int v0, int w0) : v(v0), w(w0) { }
bool operator<(const node &b) const {
return w < b.w;
}
};
bool vis[SPFA_MAX];
vector<node> vc[SPFA_MAX];
int dis[SPFA_MAX], in_que_sum[SPFA_MAX];
int n, m;
inline bool spfa(int s) {
deque<int> dq;
register int now, to;
fill(dis + 1, dis + n + 1, INF), fill(vis + 1, vis + n + 1, false), fill(in_que_sum + 1, in_que_sum + n + 1, 0);
dis[s] = 0, dq.push_back(s), vis[s] = true, in_que_sum[s]++;
while (!dq.empty()) {
now = dq.front(), dq.pop_front(), vis[now] = false;
for (register int i = 0; i < vc[now].size(); i++) {
to = vc[now][i].v;
if ((dis[now] < INF) && (dis[to] > dis[now] + vc[now][i].w)) {
dis[to] = dis[now] + vc[now][i].w;
if (!vis[to]) {
vis[to] = true, in_que_sum[to]++;
if (in_que_sum[to] == n) return false;
if ((!dq.empty()) && (dis[to] <= dis[dq.front()]))
dq.push_front(to);
else
dq.push_back(to);
}
}
}
}
return true;
}
|
