SPFA (Shortest Path Faster Algorithm)

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Basic SPFA implementation using a FIFO queue.
5
// Reads: n m s, then m edges (u v w) 1-indexed.
6
// Prints shortest distances or INF if unreachable; prints NEGATIVE CYCLE if detected.
7
8
struct Edge {
9
    int to;
10
    long long w;
11
};
12
13
const long long INF = (1LL << 60);
14
15
int main() {
16
    ios::sync_with_stdio(false);
17
    cin.tie(nullptr);
18
19
    int n, m, s;
20
    if (!(cin >> n >> m >> s)) {
21
        return 0;
22
    }
23
24
    vector<vector<Edge>> g(n + 1);
25
    for (int i = 0; i < m; ++i) {
26
        int u, v; long long w;
27
        cin >> u >> v >> w;
28
        g[u].push_back({v, w});
29
    }
30
31
    vector<long long> dist(n + 1, INF);
32
    vector<int> cnt(n + 1, 0);          // enqueue counts per vertex
33
    vector<char> inq(n + 1, 0);          // whether currently in queue
34
35
    queue<int> q;
36
    dist[s] = 0;
37
    q.push(s);
38
    inq[s] = 1;
39
    cnt[s] = 1;
40
41
    bool negCycle = false;
42
43
    while (!q.empty() && !negCycle) {
44
        int u = q.front(); q.pop();
45
        inq[u] = 0;
46
47
        if (dist[u] == INF) continue; // unreachable; skip
48
49
        for (const auto &e : g[u]) {
50
            int v = e.to;
51
            long long nd = dist[u] + e.w;
52
            if (nd < dist[v]) {
53
                dist[v] = nd;
54
                if (!inq[v]) {
55
                    q.push(v);
56
                    inq[v] = 1;
57
                    if (++cnt[v] >= n) {
58
                        // A vertex entered queue n times: negative cycle reachable
59
                        negCycle = true;
60
                        break;
61
                    }
62
                }
63
            }
64
        }
65
    }
66
67
    if (negCycle) {
68
        cout << "NEGATIVE CYCLE\n";
69
        return 0;
70
    }
71
72
    for (int v = 1; v <= n; ++v) {
73
        if (dist[v] >= INF/2) cout << "INF\n";
74
        else cout << dist[v] << "\n";
75
    }
76
77
    return 0;
78
}
79

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// SPFA with two practical heuristics:
5
// - SLF (Small Label First): push_front if new label is smaller than front's label.
6
// - LLL (Large Label Last): if popped vertex has larger label than queue average, defer it.
7
// Input: n m s, then m edges (u v w) 1-indexed. Output distances or NEGATIVE CYCLE.
8
9
struct Edge { int to; long long w; };
10
const long long INF = (1LL << 60);
11
12
int main(){
13
    ios::sync_with_stdio(false);
14
    cin.tie(nullptr);
15
16
    int n, m, s;
17
    if(!(cin >> n >> m >> s)) return 0;
18
19
    vector<vector<Edge>> g(n+1);
20
    for(int i=0;i<m;++i){
21
        int u,v; long long w; cin >> u >> v >> w;
22
        g[u].push_back({v,w});
23
    }
24
25
    vector<long long> dist(n+1, INF);
26
    vector<int> cnt(n+1, 0);
27
    vector<char> inq(n+1, 0);
28
29
    deque<int> dq;
30
    dist[s]=0; dq.push_back(s); inq[s]=1; cnt[s]=1;
31
32
    // Maintain approximate average of labels currently in deque for LLL
33
    long double sumInQ = 0.0L; sumInQ += 0; // dist[s] = 0
34
35
    bool negCycle = false;
36
37
    auto push_vertex = [&](int v){
38
        // SLF: compare with front
39
        if (!dq.empty() && dist[v] < dist[dq.front()]) {
40
            dq.push_front(v);
41
        } else {
42
            dq.push_back(v);
43
        }
44
        inq[v]=1;
45
        sumInQ += (long double)dist[v];
46
    };
47
48
    while(!dq.empty() && !negCycle){
49
        int u = dq.front(); dq.pop_front();
50
        inq[u]=0;
51
        sumInQ -= (dist[u] >= INF/2 ? 0.0L : (long double)dist[u]);
52
53
        // LLL: if dist[u] is larger than average of current queue, defer it
54
        if(!dq.empty()){
55
            long double avg = sumInQ / (long double)dq.size();
56
            if ((long double)dist[u] > avg) {
57
                // Defer u
58
                if (!dq.empty() && dist[u] < dist[dq.front()]) dq.push_front(u);
59
                else dq.push_back(u);
60
                inq[u]=1;
61
                sumInQ += (dist[u] >= INF/2 ? 0.0L : (long double)dist[u]);
62
                continue;
63
            }
64
        }
65
66
        if (dist[u] == INF) continue;
67
68
        for(const auto &e: g[u]){
69
            int v = e.to;
70
            long long nd = dist[u] + e.w;
71
            if(nd < dist[v]){
72
                dist[v] = nd;
73
                if(!inq[v]){
74
                    push_vertex(v);
75
                    if(++cnt[v] >= n){ negCycle = true; break; }
76
                }
77
            }
78
        }
79
    }
80
81
    if(negCycle){ cout << "NEGATIVE CYCLE\n"; return 0; }
82
83
    for(int v=1; v<=n; ++v){
84
        if(dist[v] >= INF/2) cout << "INF\n"; else cout << dist[v] << "\n";
85
    }
86
    return 0;
87
}
88

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Solve system of constraints: x_v - x_u <= w for m constraints.
5
// Build edges u -> v with weight w, add super-source 0 -> i with 0.
6
// If a negative cycle is reachable, the system is infeasible.
7
// Otherwise, dist[i] gives one feasible assignment for x_i.
8
9
struct Edge { int to; long long w; };
10
const long long INF = (1LL<<60);
11
12
int main(){
13
    ios::sync_with_stdio(false);
14
    cin.tie(nullptr);
15
16
    int n, m; // variables 1..n, constraints count
17
    if(!(cin >> n >> m)) return 0;
18
19
    vector<vector<Edge>> g(n+1); // we will use nodes 0..n (0 is super-source)
20
21
    for(int i=0;i<m;++i){
22
        int u, v; long long w; // constraint: x_v - x_u <= w
23
        cin >> u >> v >> w;
24
        g[u].push_back({v, w});
25
    }
26
27
    // Add super-source 0 with 0-weight edges to all variables
28
    for(int i=1;i<=n;++i) g[0].push_back({i, 0});
29
30
    vector<long long> dist(n+1, INF);
31
    vector<char> inq(n+1, 0);
32
    vector<int> cnt(n+1, 0);
33
34
    queue<int> q;
35
    dist[0] = 0; q.push(0); inq[0]=1; cnt[0]=1;
36
37
    bool negCycle=false;
38
39
    while(!q.empty() && !negCycle){
40
        int u = q.front(); q.pop(); inq[u]=0;
41
        if(dist[u] == INF) continue;
42
        for(const auto &e: g[u]){
43
            int v = e.to; long long nd = dist[u] + e.w;
44
            if(nd < dist[v]){
45
                dist[v] = nd;
46
                if(!inq[v]){
47
                    q.push(v); inq[v]=1;
48
                    if(++cnt[v] >= n+1){ // including super-source
49
                        negCycle = true; break;
50
                    }
51
                }
52
            }
53
        }
54
    }
55
56
    if(negCycle){
57
        cout << "INFEASIBLE\n";
58
    } else {
59
        cout << "FEASIBLE\n";
60
        // One feasible assignment: x_i = dist[i]
61
        for(int i=1;i<=n;++i){
62
            if(dist[i] >= INF/2) cout << "UNREACHABLE\n"; // should not happen with super-source
63
            else cout << dist[i] << "\n";
64
        }
65
    }
66
    return 0;
67
}
68