Johnson全源最短路

Johnson通过另一种方法给每条边重新标注边权。新建一个虚拟结点0，向其他所有点连一条边权为0的边，用Bellman-Ford或SPFA算法求出0到其他所有点的最短路记为gpe[i]，对于一条x->y的边权为w的边，将边权重置为w+h[x]-h[y]，以每个点为起点，跑n边dijkstra即可，时间复杂度O(nmlog2(m))。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=5e3+3;
const ll INF=1e9;
int h[N],tot,n,m,cnt[N];
ll gpe[N],dis[N];
bool in[N];
struct edge{
    int to,next,w;
}e[N<<1];
inline void add(int x,int y,int w){
    e[++tot]={y,h[x],w},h[x]=tot;
}
inline bool spfa(int s){
    queue<int>q;
    memset(gpe,0x3f,sizeof(gpe));
    memset(in,0,sizeof(in));
    gpe[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        in[x]=0;
        for(int i=h[x];i;i=e[i].next){
            int y=e[i].to;
            if(gpe[y]>gpe[x]+e[i].w){/*处理重力势能的最短路*/
                gpe[y]=gpe[x]+e[i].w;
                cnt[y]=cnt[x]+1;
                if(cnt[y]>n)return false;/*判断负环*/
                if(!in[y]){
                    in[y]=1;
                    q.push(y);
                }
            }
        }
    }
    return true;
}
inline void dijkstra(int s){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;i++)dis[i]=INF;/*初始化*/
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(in[x])continue;
        in[x]=1;
        for(int i=h[x];i;i=e[i].next){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].w){
                dis[y]=dis[x]+e[i].w;
                q.push({dis[y],y});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    for(int i=1;i<=n;i++)add(0,i,0);/*虚拟结点连边*/
    if(!spfa(0))return cout<<-1,0;
    for(int x=1;x<=n;x++)for(int i=h[x];i;i=e[i].next)e[i].w+=gpe[x]-gpe[e[i].to];/*重新修改边权*/
    for(int i=1;i<=n;i++){
        dijkstra(i);
        ll ans=0;
        for(int j=1;j<=n;j++){
            if(dis[j]==INF)ans+=j*INF;
            else ans+=j*(dis[j]+gpe[j]-gpe[i]);/*计算出新的边权*/
        }
        cout<<ans<<'\n';
    }
    return 0;
}