跳转至

最短路

Floyed 算法

\(O(n^3)\)

模版
C++
1
2
3
4
5
6
7
for (int k = 1 ; k <= n ; k++) {
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= n ; j++) {
            a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
        }
    }
}
例题

B3647 【模板】Floyd 算法 - 洛谷

Bellman-Ford 算法

\(O(nm)\)

模版
C++
 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
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
struct Node {
    int to, val;
    Node() = default;
    Node(int to, int val) : to(to), val(val) {}
};
vector<Node> adj[200005];
int dist[200005];
int n;
void bellman_ford(int s) {
    for (int i = 1 ; i <= n ; i++) {
        dist[i] = 0x7fffffff;
    }
    dist[s] = 0;
    for (int i = 1 ; i <= n ; i++) {
        bool flag = false;
        for (int p = 1 ; p <= n ; p++) {
            if (dist[p] == 0x7fffffff) {
                continue;
            }
            for (auto &[to, val] : adj[p]) {
                if (dist[p] + val < dist[to]) {
                    dist[to] = dist[p] + val;
                    flag = true;
                }
            }
        }
        if (flag == false) {
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, s;
    cin >> n >> m >> s;
    for (int i = 0 ; i < m ; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        adj[u].emplace_back(v, val);
    }
    bellman_ford(s);
    for (int i = 1 ; i <= n ; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}
例题

P3371 【模板】单源最短路径（弱化版） - 洛谷

Spfa 算法

\(O(nm)\)

模版
C++
 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
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
struct Node {
    int to, val;
    Node() = default;
    Node(int to, int val) : to(to), val(val) {}
};
int dist[10005];
bool vis[10005];
vector<Node> adj[10005];
int n;
void spfa(int s) {
    for (int i = 1 ; i <= n ; i++) {
        dist[i] = 0x7fffffff;
        vis[i] = false;
    }
    queue<int> que;
    que.emplace(s);
    dist[s] = 0;
    vis[s] = true;
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        vis[p] = false;
        for (auto &[to, val] : adj[p]) {
            if (dist[p] + val < dist[to]) {
                dist[to] = dist[p] + val;
                if (vis[to] == false) {
                    vis[to] = true;
                    que.emplace(to);
                }
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, s;
    cin >> n >> m >> s;
    for (int i = 0 ; i < m ; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        adj[u].emplace_back(v, val);
    }
    spfa(s);
    for (int i = 1 ; i <= n ; i++) {
        cout << dist[i] << " \n"[i == n];
    }
    return 0;
}
例题

P3371 【模板】单源最短路径（弱化版） - 洛谷

P3385 【模板】负环 - 洛谷

判断是否有负环(路径和为负数的环)

代码
C++
 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
struct Node {
    int to, val;
    Node() = default;
    Node(int to, int val) : to(to), val(val) {}
};
long long dist[2005];
bool vis[2005];
int cnt[2005];
vector<Node> adj[2005];
int n;
bool spfa(int s) {
    for (int i = 1 ; i <= n ; i++) {
        dist[i] = 0x7fffffffffffffff;
        vis[i] = false;
        cnt[i] = 0;
    }
    queue<int> que;
    que.emplace(s);
    dist[s] = 0;
    vis[s] = true;
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        vis[p] = false;
        for (auto &[to, val] : adj[p]) {
            if (dist[p] + val < dist[to]) {
                dist[to] = dist[p] + val;
                if (vis[to] == false) {
                    vis[to] = true;
                    if (++cnt[to] >= n) {
                        return true;
                    }
                    que.emplace(to);
                }
            }
        }
    }
    return false;
}
bool solve() {
    int m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        adj[i].clear();
    }
    for (int i = 0 ; i < m ; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        if (val >= 0) {
            adj[v].emplace_back(u, val);
        }
        adj[u].emplace_back(v, val);
    }
    return spfa(1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cout << (solve() ? "YES\n" : "NO\n");
    }
    return 0;
}

Dijkstra 算法

\(O(m\log m)\)

模版
C++
 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
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
struct Node {
    int to, val;
    Node() = default;
    Node(int to, int val) : to(to), val(val) {}
    bool operator<(const auto &x) const {
        return val > x.val;
    }
};
vector<Node> adj[200005];
int dist[200005];
bool vis[200005];
int n;
void dijkstra(int s) {
    for (int i = 1 ; i <= n ; i++) {
        dist[i] = 0x7fffffff;
        vis[i] = false;
    }
    dist[s] = 0;
    priority_queue<Node> que;
    que.emplace(s, 0);
    while (!que.empty()) {
        auto x = que.top().to;
        que.pop();
        if (vis[x] == true) {
            continue;
        }
        vis[x] = true;
        for (auto &[to, val] : adj[x]) {
            if (dist[x] + val < dist[to]) {
                dist[to] = dist[x] + val;
                que.emplace(to, dist[to]);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, s;
    cin >> n >> m >> s;
    for (int i = 0 ; i < m ; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        adj[u].emplace_back(v, val);
    }
    dijkstra(s);
    for (int i = 1 ; i <= n ; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}
例题

P4779 【模板】单源最短路径（标准版） - 洛谷

Johnson 全源最短路径算法

\(O(nm\log m)\)

跑一遍 spfa 判负环，后跑 n 遍 dijkstra

模版
C++
  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
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
struct Node {
    int to, val;
    Node() = default;
    Node(int to, int val) : to(to), val(val) {}
    bool operator<(const auto &x) const {
        return val > x.val;
    }
};
int h[3005];
int dist[3005];
int cnt[3005];
bool vis[3005];
vector<Node> adj[3005];
int n;
bool spfa() {
    for (int i = 1 ; i <= n ; i++) {
        h[i] = 0x7fffffff;
        vis[i] = false;
        cnt[i] = 0;
        adj[0].emplace_back(i, 0);
    }
    queue<int> que;
    que.emplace(0);
    h[0] = 0;
    vis[0] = true;
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        vis[p] = false;
        for (auto &[to, val] : adj[p]) {
            if (h[p] + val < h[to]) {
                h[to] = h[p] + val;
                if (vis[to] == false) {
                    vis[to] = true;
                    if (++cnt[to] >= n) {
                        return true;
                    }
                    que.emplace(to);
                }
            }
        }
    }
    return false;
}
void dijkstra(int s) {
    for (int i = 1 ; i <= n ; i++) {
        dist[i] = 0x7fffffff;
        vis[i] = false;
    }
    dist[s] = 0;
    priority_queue<Node> que;
    que.emplace(s, 0);
    while (!que.empty()) {
        auto x = que.top().to;
        que.pop();
        if (vis[x] == true) {
            continue;
        }
        vis[x] = true;
        for (auto &[to, val] : adj[x]) {
            if (dist[x] + val < dist[to]) {
                dist[to] = dist[x] + val;
                que.emplace(to, dist[to]);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int u, v, val;
        cin >> u >> v >> val;
        adj[u].emplace_back(v, val);
    }
    if (spfa()) {
        cout << -1 << "\n";
        return 0;
    }
    for (int i = 1 ; i <= n ; i++) {
        for (auto &[to, val] : adj[i]) {
            val += h[i] - h[to];
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        dijkstra(i);
        long long ans = 0;
        for (int j = 1 ; j <= n ; j++) {
            if (dist[j] == 0x7fffffff) {
                ans += j * 1000000000L;
            } else {
                ans += 1LL * j * (dist[j] + h[j] - h[i]);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}
例题

P5905 【模板】Johnson 全源最短路 - 洛谷