最短路

最短路算法	\(SPFA\)	\(Dijkstra\)	\(Johnson\)
最短路类型	单源最短路	单源最短路	每对结点之间的最短路
作用于	任意图	非负权图	任意图
能否检测负环？	能	不能	能
时间复杂度	\(O(NM)\)	\(O(M\log M)\)	\(O(NM\log M)\)

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#define INF 0x7fffffff
const int N = 1e5 + 10; // 点
const int M = 5e5 + 10; // 边

struct node
{
    int dis, id;
    bool operator<(const node &a) const { return dis > a.dis; }
    node(int d, int x) { dis = d, id = x; }
};

vector<pair<int, int>> g[N];
int dis[N];
bool vis[N];
int n, m, k; // k 出发点

void dijkstra()
{
    priority_queue<node> q;
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[k] = 0;
    q.push(node(0, k));
    while (!q.empty())
    {
        int u = q.top().id;
        q.pop();

        if (vis[u])
            continue;
        vis[u] = true;

        for (int i = 0; i < g[u].size(); i++)
        {
            int v = g[u][i].first, w = g[u][i].second;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
	            if (!vis[v])
			        q.push(node(dis[v], v));
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << dis[i] << ' ';
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const int N = 1e5 + 10;

vector<pair<int, int>> e[N];
int dis[N], cnt[N], vis[N];

bool spfa(int n, int s)
{
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 0, vis[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first, w = e[u][i].second;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
                if (cnt[v] >= n)
                    return false;
                // 在不经过负环的情况下，最短路至多经过 n - 1 条边
                // 因此如果经过了多于 n 条边，一定说明经过了负环
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return true;
}

Johnson

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e9

struct edge
{
    int v, w;
    edge(int _v, int _w) : v(_v), w(_w) {}
};

struct node
{
    int dis, id;
    bool operator<(const node &a) const { return dis > a.dis; }
    node(int d, int x) : dis(d), id(x) {}
};

vector<vector<edge>> adj;
vector<int> vis, t;
vector<ll> h, dis;
int n, m;

void addedge(int u, int v, int w)
{
    adj[u].push_back(edge(v, w));
}

bool spfa(int s)
{
    queue<int> q;
    h.assign(h.size(), INF);
    h[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto &e : adj[u])
        {
            int v = e.v, w = e.w;
            if (h[v] > h[u] + w)
            {
                h[v] = h[u] + w;
                if (!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                    t[v]++;
                    if (t[v] == n + 1)
                        return false;
                }
            }
        }
    }
    return true;
}

void dijkstra(int s)
{
    priority_queue<node> q;
    dis.assign(dis.size(), INF);
    vis.assign(vis.size(), 0);
    dis[s] = 0;
    q.push(node(0, s));
    while (!q.empty())
    {
        int u = q.top().id;
        q.pop();

        if (vis[u])
            continue;
        vis[u] = 1;

        for (auto &e : adj[u])
        {
            int v = e.v, w = e.w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!vis[v])
                    q.push(node(dis[v], v));
            }
        }
    }
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    cin >> n >> m;
    adj.resize(n + 1);
    vis.resize(n + 1);
    t.resize(n + 1);
    h.resize(n + 1);
    dis.resize(n + 1);

    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        addedge(u, v, w);
    }
    for (int i = 1; i <= n; i++)
        addedge(0, i, 0);

    if (!spfa(0))
    {
        cout << -1 << endl;
        return 0;
    }

    for (int u = 1; u <= n; u++)
        for (auto &e : adj[u])
            e.w += h[u] - h[e.v];

    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] + h[j] - h[i]);
        }
        cout << ans << endl;
    }

    return 0;
}