模板题目
// 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;
}
原理解释：
众所周知，全源最短路可以通过枚举起点，跑过 \(n\) 次 \(\text{Bellman-Ford}\) 算法解决，其复杂度大小为 \(O(n^2m)\)，或者直接使用 \(\text{Floyd}\) 算法解决，其复杂度较高，为 \(O(n^3)\)。
当然，我们可以使用堆优化的 \(\text{Dijkstra}\) 算法，它的复杂度可以到达 \(O(nm \log m)\)，比 \(\text{Bellman-Ford}\) 更加优秀。然而它有局限性：即不能处理负权边的情况。因此我们需要先对图进行预处理，确保所有边的边权均非负。
一种思路是通过给每条边权加上一个数，使得所有的边权都不为负数，但是这样的做法是错误的，源点所经过最短路上的节点数量不同，多加上的边权也不同。
第二种即为 \(\text{Johnson}\) 算法的核心思路：
-
通过新建立一个虚拟节点（一般为 \(0\)），通过 \(\text{Bellman-Ford}\) 算法求出该点到其他点的所有最短路，记作 \(h_{i}\)。
-
假如有一条起点为 \(u\)，出点为 \(v\)，边权为 \(w\) 的点，我们将这个点的边权设置为 \(w + h_{u} - h_{v}\)。
-
接下来跑 \(n\) 次 \(\text{Dijkstra}\) 就可以求出全源最短路了。
该思想证明如下：
代码实现
判断负环
根据 \(\text{Bellman-Ford}\) 算法，我们在对图进行 \(n\) 次松弛后如果还可以进行松弛，则说明进入了死循环当中，也说明存在负环。
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 + h_{u} - h_{v}\)，同样也可以通过 \(\text{Bellman-Ford}\) 算法实现。
for (int i = 1; i <= n; i++)
for (auto &y : g[i])
y.w = y.w + h[i] - h[y.x];
for(int x = 1;x <= n; ++ x)
for(auto &[y, w] : g[x])
w = w + h[x] - h[y];
求单源最短路
学习Dijkstra算法同时定义一个二位 dis 数组记录两点最短距离。
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];
}
处理数据
通过 \(\text{Dijkstra}\) 得到的距离是经过预处理的，因此我们需要最后处理一遍变成原来的数据，减回去即可。
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];
初始化&主函数
#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 为源点的单源最短路数组
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;
}