模板题目

www.luogu.com.cn

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
105
106
107
108
109
110
111
112
113
114
// Problem: P5905 【模板】全源最短路（Johnson）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5905
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long

const int N = 3e3 + 9;
const int INF = 1e9;

int n, m, h[N], dis[N][N];
struct Edge { int x, y, w; };
struct Node
{
    int x, w;
    bool operator < (const Node &u) const { return w == u.w ? x < u.x : w > u.w; }
};
vector <Node> g[N];
vector <Edge> bg;

bool Bellman_Ford()
{
    for (int i = 1; i <= n; i++) h[i] = INF;
    for (int i = 1; i <= n; i++)
    {
        for (auto &m : bg)
        {
            if (h[m.x] == INF) continue;
            if (h[m.x] + m.w < h[m.y])
                h[m.y] = h[m.x] + m.w;	
        }
    }
    for (auto &m : bg)
    {
        if (h[m.x] == INF) continue;
        if (h[m.x] + m.w < h[m.y]) return false;
    }
    return true;
}

void dijkstra(int st)
{
    int d[N];
    bitset <N> vis;
    for (int i = 1; i <= n; i++) d[i] = INF;
    priority_queue <Node> pq;
    d[st] = 0;
    pq.push({st, d[st]});
    while (!pq.empty())
    {
        int x = pq.top().x; pq.pop();
        if (vis[x] == true) continue;
        vis[x] = true;
        for (auto &m : g[x])
        {
            if (d[x] + m.w < d[m.x])
            {
                d[m.x] = d[x] + m.w;
                pq.push({m.x, d[m.x]});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        dis[st][i] = d[i];
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        bg.push_back({u, v, w});
    }
    for (int i = 1; i <= n; i++)
        bg.push_back({0, i, 0});
        
    if (!Bellman_Ford())
    {
        cout << -1 << '\n';
        return 0;
    }
    
    for (int i = 1; i <= n; i++)
        for (auto &y : g[i])
        {
            y.w = y.w + h[i] - h[y.x];
            // cout << y.w << ' ';
        }
    
            
    for (int i = 1; i <= n; i++)
        dijkstra(i);
    for (int i = 1; i <= n; i++)
    {
        int sum = 0;
        for (int j = 1; j <= n; j++)
        {
            if (dis[i][j] == INF) sum += 1ll * j * INF;
            else sum += 1ll * j * (dis[i][j] - h[i] + h[j]);
        }
        cout << sum << '\n';	
    }
    return 0;
}

Johnson全源最短路，物理与信息学的巧妙结合

原理解释：

众所周知，全源最短路可以通过枚举起点，跑过 nn 次 Bellman-Ford\text{Bellman-Ford} 算法解决，其复杂度大小为 O(n2m)O(n^2m)，或者直接使用 Floyd\text{Floyd} 算法解决，其复杂度较高，为 O(n3)O(n^3)。

当然，我们可以使用堆优化的 Dijkstra\text{Dijkstra} 算法，它的复杂度可以到达 O(nmlog⁡m)O(nm \log m)，比 Bellman-Ford\text{Bellman-Ford} 更加优秀。然而它有局限性：即不能处理负权边的情况。因此我们需要先对图进行预处理，确保所有边的边权均非负。

一种思路是通过给每条边权加上一个数，使得所有的边权都不为负数，但是这样的做法是错误的，源点所经过最短路上的节点数量不同，多加上的边权也不同。

第二种即为 Johnson\text{Johnson} 算法的核心思路：

  • 通过新建立一个虚拟节点（一般为 00），通过 Bellman-Ford\text{Bellman-Ford} 算法求出该点到其他点的所有最短路，记作 hih_{i}。

  • 假如有一条起点为 uu，出点为 vv，边权为 ww 的点，我们将这个点的边权设置为 w+hu−hvw + h_{u} - h_{v}。

  • 接下来跑 nn 次 Dijkstra\text{Dijkstra} 就可以求出全源最短路了。

该思想证明如下：

https://i0.hdslb.com/bfs/article/375adf3246b18f05016ecaa78c1d2044231911980.png@1256w_352h_!web-article-pic.webp

代码实现

判断负环

根据 Bellman-Ford\text{Bellman-Ford} 算法，我们在对图进行 nn 次松弛后如果还可以进行松弛，则说明进入了死循环当中，也说明存在负环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll h[N];//h[x]表示源点0到到x的最短距离，通过Bellman-Ford计算

bool Bellman_Ford()
{
    for (int i = 1; i <= n; i++) h[i] = INF;
    for (int i = 1; i <= n; i++)
    {
        for (auto &m : bg)
        {
            if (h[m.x] == INF) continue;
            if (h[m.x] + m.w < h[m.y])
                h[m.y] = h[m.x] + m.w;	
        }
    }
    for (auto &m : bg)
    {
        if (h[m.x] == INF) continue;
        if (h[m.x] + m.w < h[m.y]) return false;
    }
    return true;
}

调整权重

我们需要将每条边的权重调整为 w+hu−hvw + h_{u} - h_{v}，同样也可以通过 Bellman-Ford\text{Bellman-Ford} 算法实现。

1
2
3
for (int i = 1; i <= n; i++)
        for (auto &y : g[i])
            y.w = y.w + h[i] - h[y.x];
1
2
3
for(int x = 1;x <= n; ++ x)
    for(auto &[y, w] : g[x])
        w = w + h[x] - h[y];

求单源最短路

学习Dijkstra算法同时定义一个二位 dis 数组记录两点最短距离。

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
void dijkstra(int st)
{
    int d[N];
    bitset <N> vis;
    for (int i = 1; i <= n; i++) d[i] = INF;
    priority_queue <Node> pq;
    d[st] = 0;
    pq.push({st, d[st]});
    while (!pq.empty())
    {
        int x = pq.top().x; pq.pop();
        if (vis[x] == true) continue;
        vis[x] = true;
        for (auto &m : g[x])
        {
            if (d[x] + m.w < d[m.x])
            {
                d[m.x] = d[x] + m.w;
                pq.push({m.x, d[m.x]});
            }
        }
    }
  
    for (int i = 1; i <= n; i++)
        dis[st][i] = d[i];
}

处理数据

通过 Dijkstra\text{Dijkstra} 得到的距离是经过预处理的，因此我们需要最后处理一遍变成原来的数据，减回去即可。

1
2
3
for(int i = 1;i <= n; ++ i)
        for(int j = 1;j <= n; ++ j)
            cout << (dis[i][j] == INF ? INF : dis[i][j] - h[i] + h[j]) << " \n"[j == n];

初始化&主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long

const int N = 3e3 + 9;
const int INF = 1e9;

int n, m, h[N], dis[N][N];// h[x]表示源点0到到x的最短距离，通过Bellman-Ford计算
                          // dis[i][j]表示i到j的最短路
struct Edge{
    int x, y, w; // 入点，出点，边权
};

struct Node{
    int x, w;
    bool operator < (const Node &u)const {
        return w == u.w ? x < u.x : w > u.w; // 大根堆变为小根堆
    }
};

vector <Node> g[N]; // 存图
vector <Edge> bg;   // 以 0 为源点的单源最短路数组
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
igned main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
  
    for (int i = 1; i <= m; i++) // 存图
    {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        bg.push_back({u, v, w});
    }
  
    for (int i = 1; i <= n; i++)
        bg.push_back({0, i, 0}); // 将所有便与 0点 的距离存入图中
        
    if (!Bellman_Ford()) // 如果有负环，则输出 -1，同时处理了权重
    {
        cout << -1 << '\n';
        return 0;
    }
    
    for (int i = 1; i <= n; i++) // 将所有权重全部处理掉
        for (auto &y : g[i])
            y.w = y.w + h[i] - h[y.x];

    for (int i = 1; i <= n; i++) // 求各个点的单源最短路
        dijkstra(i);
  
    for(int i = 1;i <= n; ++ i)
        for(int j = 1;j <= n; ++ j)
            cout << (dis[i][j] == INF ? INF : dis[i][j] - h[i] + h[j]) << " \n"[j == n];
    return 0;
}