Johnson全源最短路：
n个点m条边
Johnson全源最短路算法
主要解决负环问题的全源最短路径算法
主要思路：
1.SPFA判断负环，在跑SPFA之前建立一个[超级源点]标号为0
与每一个点之间都存在一条 长度为0的路径
跑SPFA记录[0]到每个点的最短路 记为 h[i]
用此方法可以标记存在的负环
2.在跑Dijkstra之前调整每条边边权为非负
若u->v边权为w 那么将每条边边权都增加 h[u]-h[v]，统计答案时需减去
证明：先画个图，利用三角形三边关系定理可得 w+h[u]>=h[v]
移项可得 w+h[u]-h[v]>=0 所以在w上加 h[u]-h[v]即可保证非负
3.跑n次Dijkstra(堆优化) 复杂度为O(n^2logm)
算法时间复杂度为O(n^2logm)
My_Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const ll N=1e4+6010;
const ll inf=1e9;
ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
ll head[N],to[N*2],dis[N*2],nxt[N*2],tot=0;
void add(int u,int v,int w) {
nxt[++tot]=head[u];
to[tot]=v;
dis[tot]=w;
head[u]=tot;
}
ll n,m;
ll h[N],cnt[N];
ll vis[N];
bool spfa(ll s) {
queue<ll> p;
for(ll i=1; i<=n; i++) {
h[i]=inf;
vis[i]=false;
cnt[N]=0;
}
p.push(s);
h[s]=0;
cnt[s]++;
vis[s]=true;
while(!p.empty()) {
ll u=p.front();
p.pop();
vis[u]=false;
for(ll i=head[u]; i; i=nxt[i]) {
ll v=to[i],w=dis[i];
if(h[v]>h[u]+w) {
h[v]=h[u]+w;
if(vis[v]==false) {
p.push(v);
vis[v]=true;
cnt[v]++;
if(cnt[v]>=n+1) return true;
}
}
}
}
return false;
}
ll d[N];
void Dijkstra(ll s) {
priority_queue<pair<ll,ll>> q;
for(ll i=1; i<=n; i++) {
d[i]=inf;
vis[i]=0;
}
d[s]=0;
q.push(make_pair(0,s));
while(!q.empty()) {
ll u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(ll i=head[u]; i; i=nxt[i]) {
ll v=to[i],w=dis[i];
if(d[v]>d[u]+w) {
d[v]=d[u]+w;
q.push(make_pair(-d[v],v));
}
}
}
}
signed main() {
n=read();
m=read();
for(int i=1; i<=m; i++) {
int u=read(),v=read(),w=read();
add(u,v,w);
}
for(int i=1; i<=n; i++) {
add(0,i,0);//加入超级源点0
}
if(spfa(0)) {
printf("-1\n");
return 0;
}
for(int u=1; u<=n; u++) {
for(int i=head[u]; i; i=nxt[i]) {
int v=to[i];
dis[i]+=(h[u]-h[v]);
}
}
for(int i=1; i<=n; i++) {
Dijkstra(i);
int ans=0;
for(int j=1; j<=n; j++) {
if(d[j]==inf) ans+=inf*j;
else ans+=j*(d[j]-(h[i]-h[j]));
}
printf("%lld\n",ans);
}
return 0;
}