本文共 2689 字，大约阅读时间需要 8 分钟。

P5905 【模板】Johnson 全源最短路

代码实现

#include 
   
    using namespace std;const int N = 5005;const int M = 60006;const int INF = 1e9;struct edge {
       long long v, w, next;} e[M];struct node {
       int id;    long long w;    const bool operator<(const node &a) const {
           return a.w < w;    }};int cnt, n, m;int head[M], inq[M], vis[M], num[N];long long dis[M], ndis[M];void add(int u, int v, int w) {
       cnt++;    e[cnt].v = v;    e[cnt].w = w;    e[cnt].next = head[u];    head[u] = cnt;}bool spfa(int s) {
       queue
    
      q;    for (int i = 1; i <= n; i++) {
           dis[i] = INF, inq[i] = 0;    }    inq[s] = 1;    dis[s] = 0;    q.push(s);    while (!q.empty()) {
           int fro = q.front();        q.pop();        inq[fro] = 0;        for (int i = head[fro]; i; i = e[i].next) {
               int nv = e[i].v;            if (dis[nv] > dis[fro] + e[i].w) {
                   dis[nv] = dis[fro] + e[i].w;                if (!inq[nv]) {
                       inq[nv] = 1;                    q.push(nv);                    if (++num[nv] >= n + 1) {
                           return 1;                    }                }            }        }    }    return 0;}void Dijkstra(int s) {
       priority_queue
     
       Q;    for (int i = 1; i <= n; i++) ndis[i] = INF, vis[i] = 0;    ndis[s] = 0;    Q.push((node) {
   s, 0});    while (!Q.empty()) {
           int fro = Q.top().id;        Q.pop();        if (vis[fro]) {
               continue;        }        vis[fro] = 1;        for (int i = head[fro]; i; i = e[i].next) {
               int nv = e[i].v;            if (ndis[nv] > ndis[fro] + e[i].w) {
                   ndis[nv] = ndis[fro] + e[i].w;                if (!vis[nv]) {
                       Q.push({
   nv, ndis[nv]});                }            }        }    }    return;}int main() {
       cin >> n >> m;    for (int i = 0; i < m; i++) {
           int u, v, w;        cin >> u >> v >> w;        add(u, v, w);    }    for (int i = 1; i <= n; i++) {
           add(0, i, 0);    }    if (spfa(0)) {
           // 若图中存在负环，输出-1        cout << -1;        return 0;    }    for (int i = 1; i <= n; i++) {
           for (int j = head[i]; j; j = e[j].next) {
               e[j].w += dis[i] - dis[e[j].v];        }    }    //  dis[i][j]为从 i 到 j 的最短路，    //  在第 i 行输出 从1到n j*dis[i][j] 的累加    for (int i = 1; i <= n; i++) {
           Dijkstra(i);        long long ans = 0;        for (int j = 1; j <= n; j++) {
               if (ndis[j] == INF) {
                   ans += 1ll * j * INF;            } else {
                   ans += 1ll * j * (ndis[j] + dis[j] - dis[i]);            }        }        cout << ans << endl;    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/111871540 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！