Johnson 全源最短路
Johnson 和 Floyd 一样是能求出无负环图上任意两点间最短路径的算法。
引入
求任意两点间的最短路可以通过枚举起点，跑 (n) 次 SPFA 来解决，时间复杂度是 (O(n^2 m)) 的，也可以用 Floyd 解决，复杂度为 (O(n^3))。
或者我们可以跑 (n) 次堆优化的 Dijkstra，复杂度为 (O(nmlog m))。
但是 Dijkstra 有一个致命的缺陷就是他不能处理负边权。
我们不难想到来修改边权使其为正数。
核心思想
我们新建一个虚拟的节点，假设他的编号为 (0)，从这个点向其他所有点连一条边权为 (0) 的边。
接下来我们跑一遍 SPFA，求出零号点到所有点的最短路记为 (h_{i})，顺便判断一下有没有负环。
如果存在一条边 ((u,v,w))，我们将其修改为 ((u,v, w+h_{i}-h_{v}))。
接下来以每一个点为起点跑 (n) 边 Dijkstra 就好了。
复杂度为 (O(nm log m))
正确性
我们考虑找到从 (s) 到 (t) 的一条路径为：
]
那么这条路径的长度就是：
(w(pk, t) + h_{pk} – h_{t})
]
展开就是：
]
所以无论怎么走，只要是 (sto t) 的一条最短路径，那么最后就是比原答案多了 (h_{s}-h_{t})。
Q：你说的对，但是为什么能保证修改后的边权都是非负数？
根据 (h_{v}le h_{u} + w(u,v))，稍微变化一下就是 (h_{u} + w(u,v) – h_{v} ge 0)，所以图中的边权均为非负。
code
#include
#define pii pair
#define INF 1000000000
#define int long long
#define N 10010
#define endl 'n'
using namespace std;
inline 服务器托管网int read()
{
int x = 0, f = 1;
char c = getchar();
while(c 服务器托管网 '9'){if(c == '-') f = -1; c = getchar();}
while(c = '0') x = (x q;
memset(vis, 0, sizeof vis);
for(int i = 1; i h[u] + w)
{
h[v] = h[u] + w;
if(!vis[v])
{
vis[v] = 1;
cnt[v] ++;
q.push(v);
if(cnt[v] == n + 1) return 0;
}
}
}
}
return 1;
}
inline void dijkstra(int s)
{
priority_queue, greater > q;
memset(vis, 0, sizeof vis);
for(int i = 1; i 参考文章：https://zhuanlan.zhihu.com/p/99802850
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
动动发财的小手，点个赞吧！ 在本教程中，我们将学习如何反转 ggplot2 中图例键的顺序。 在 ggplot2 中，当我们在 aes() 中使用颜色或填充参数为变量着色时，我们会得到一个带有键的图例，显示哪些键匹配哪些颜色。在这里，我们将展示如何使用 gui…
