「一本通 3.3 练习 3」Easy SSSP

形式化题目

给定一个包含 $N$ 个节点、 $M$ 条边的带权有向图 $G = (V, E)$ ，以及指定的源点 $S$ 。边权可能为负数。

要求执行以下判断与计算：

检测图中是否存在任意负权回路。若存在，输出一行 -1 并结束。
若图中不存在负权回路，计算源点 $S$ 到所有点 $i \in [1, N]$ 的最短路径长度：
- 到自身距离输出 0；
- 与源点 $S$ 不连通（不可达）输出 NoPath；
- 否则输出最短路数值。

样例说明

样例中源点为 $1$ 。从点 $1$ 出发：

$1 \to 1$ 距离为 0；
$1 \to 2$ 边权为 $6$ ；
$1 \to 3$ 边权为 $4$ ；
$1 \to 3 \to 4$ 路径长为 $4 + (-7) = -3$ ；
$1 \to 3 \to 4 \to 5$ 路径长为 $-3 + 1 = -2$ ；
$1 \to 3 \to 6$ 路径长为 $4 + 3 = 7$ 。

图中无负权回路，因此依次输出各点的最短路值。

正解

思路

本题由两个核心部分组成：全图负环检测 与 单源最短路求解。

1. 关键观察：负环是否与源点 $S$ 连通

题目要求“判断这个有向图中是否存在负权回路……如果存在负权回路，只输出一行 -1”。特别需要注意：即使负环处于一个无法从源点 $S$ 到达的独立连通块中，只要图中存在负环，也必须输出 -1。

因此，判负环不能仅从源点 $S$ 出发松弛，而必须覆盖整个图。

2. 全图判负环算法

我们可以利用虚拟超级源点 $0$ 向所有点 $1 \dots N$ 连权为 $0$ 的边，或者等价地，在 SPFA 初始化时将所有点 $1 \dots N$ 一同入队，并将 dist 初始值均设为 $0$ 。

在队列松弛过程中，维护数组 edge_cnt[v] 表示当前起点到达节点 $v$ 的最短路所包含的边数：

每次成功松弛出边 $(u, v, w)$ 时，更新 edge_cnt[v] = edge_cnt[u] + 1；
根据抽屉原理，若 edge_cnt[v] >= N，说明该简单路径上至少包含 $N+1$ 个顶点，必有顶点被重复访问，即图中必然存在负权回路；
此时可立即终止算法并输出 -1。

3. 单源最短路（SSSP）

若全图不存在负权回路，则以 $S$ 为唯一起点重新运行一次 SPFA：

初始化 dist[S] = 0，其余点为 $\infty$ ；
将 $S$ 加入队列进行松弛更新；
遍历 $i \in [1, N]$ 输出结果： $i = S$ 输出 0，dist[i] == INF 输出 NoPath，其余输出 dist[i]。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-03-31 09:00
# update_at: 2026-03-31 09:00

import sys
from collections import deque

INF = 10**18  # 无穷大哨兵


def has_negative_cycle(n: int, adj: list[list[tuple[int, int]]]) -> bool:
    """SPFA 检查全图是否存在负权环：将所有点入队松弛，松弛边数达到 n 则存在负权环。"""
    dist = [0] * (n + 1)
    edge_cnt = [0] * (n + 1)
    in_queue = [True] * (n + 1)
    queue: deque[int] = deque(range(1, n + 1))

    while queue:
        u = queue.popleft()
        in_queue[u] = False
        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                edge_cnt[v] = edge_cnt[u] + 1
                if edge_cnt[v] >= n:
                    return True
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    return False


def shortest_paths(n: int, start: int, adj: list[list[tuple[int, int]]]) -> list[int]:
    """SPFA 求源点 start 到各点的单源最短路长度。"""
    dist = [INF] * (n + 1)
    dist[start] = 0
    in_queue = [False] * (n + 1)
    in_queue[start] = True
    queue: deque[int] = deque([start])

    while queue:
        u = queue.popleft()
        in_queue[u] = False
        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    return dist


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        token = next(data)
    except StopIteration:
        return
    n = int(token)
    m = int(next(data))
    start_node = int(next(data))

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, weight = int(next(data)), int(next(data)), int(next(data))
        adj[u].append((v, weight))

    if has_negative_cycle(n, adj):
        print("-1")
        return

    dist = shortest_paths(n, start_node, adj)
    out: list[str] = [
        "0" if i == start_node else ("NoPath" if dist[i] == INF else str(dist[i]))
        for i in range(1, n + 1)
    ]
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
136
137/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:26
 * update_at: 2026-10-05 05:26
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;    // 点数上限
const int MAXM = 100005;  // 边数上限
const long long INF = 4000000000000000000LL; // 无穷大哨兵，远大于任何合法最短路

typedef long long ll;

ll n;          // 点数
ll m;          // 边数
ll start_node; // 源点 S

int head[MAXN];  // 链式前向星：head[u] 是以 u 为起点的第一条边编号
int to[MAXM];    // to[i] 是第 i 条边的终点
int nxt_edge[MAXM]; // nxt_edge[i] 是 u 的下一条边编号
ll weight[MAXM]; // weight[i] 是第 i 条边的边权，可能为负
int edge_idx;    // 已加入的边数

ll dist[MAXN];      // dist[v] 是当前求出的到 v 的最短距离
int relax_cnt[MAXN]; // relax_cnt[v] 是当前最短路包含的边数，用于判负环
bool in_queue[MAXN]; // 标记点是否在 SPFA 队列中

// 加入一条 u -> v、权值为 w 的有向边。
void add_edge(int u, int v, ll w) {
    edge_idx++;
    to[edge_idx] = v;
    weight[edge_idx] = w;
    nxt_edge[edge_idx] = head[u];
    head[u] = edge_idx;
}

// 全图判负环：所有点一起入队（等价于建一个到各点权为 0 的超级源点）。
// 若某点的最短路已被松弛出 >= n 条边，说明路径上必有重复点，即存在负权回路。
bool has_negative_cycle() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        dist[i] = 0; // 全员初始为 0，负环在任意连通块中都能被发现
        relax_cnt[i] = 0;
        in_queue[i] = true;
        q.push(i);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (int i = head[u]; i != 0; i = nxt_edge[i]) {
            int v = to[i];
            if (dist[u] + weight[i] < dist[v]) {
                dist[v] = dist[u] + weight[i];
                relax_cnt[v] = relax_cnt[u] + 1;
                if (relax_cnt[v] >= n) {
                    return true;
                }
                if (!in_queue[v]) {
                    in_queue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return false;
}

// 以 src 为源点做 SPFA，求单源最短路；调用前保证全图无负权回路。
void shortest_path(ll src) {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        in_queue[i] = false;
    }
    dist[src] = 0;
    in_queue[src] = true;
    queue<int> q;
    q.push(src);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (int i = head[u]; i != 0; i = nxt_edge[i]) {
            int v = to[i];
            if (dist[u] + weight[i] < dist[v]) {
                dist[v] = dist[u] + weight[i];
                if (!in_queue[v]) {
                    in_queue[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

void read_input() {
    cin >> n >> m >> start_node;
    for (ll i = 1; i <= m; i++) {
        int u;
        int v;
        ll w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();

    if (has_negative_cycle()) {
        cout << -1 << "\n";
        return 0;
    }

    shortest_path(start_node);
    for (int i = 1; i <= n; i++) {
        if (i == start_node) {
            cout << 0 << "\n";
        } else if (dist[i] == INF) {
            cout << "NoPath" << "\n";
        } else {
            cout << dist[i] << "\n";
        }
    }

    return 0;
}

复杂度

时间复杂度：
- 全图负环检测阶段与 SSSP 阶段均使用 SPFA 算法，平均时间复杂度为 $O(k \cdot M)$ （ $k$ 为每个节点的平均入队常数），最坏情况下为 $O(N \cdot M)$ 。
- 本题 $N \leqslant 1000, M \leqslant 10^5$ ，完全可以在限制时间内完成。
空间复杂度：
- 邻接表存储图需要 $O(N + M)$ 空间。
- 辅助数组 dist、edge_cnt、in_queue 及队列占用 $O(N)$ 空间。
- 整体空间复杂度为 $O(N + M)$ 。

总结

解决本题的关键在于准确捕捉题面“判断这个有向图是否存在负权回路”这一全图性质，避免只从源点 $S$ 出发判环而遗漏不可达区域中的负环。先进行全局负环检测，再进行单源最短路求解，结构清晰且高效。

图示解析

本题解题主线图示：

text

1
2
3
4
5
6
7
8
9
10
11有向图 G = (V, E)
|- 第一阶段：全图负环检测（虚拟超级源点 / 全员入队）
|  |- 松弛边数 cnt[v] >= N ?
|  |  |- 是 -> 存在负权回路 -> 输出 -1
|  |  `- 否 -> 全图无负权回路 -> 进入第二阶段
`- 第二阶段：从源点 S 运行单源最短路 (SSSP)
   |- dist[S] = 0, 其他点 = INF
   `- 遍历点 i = 1..N:
      |- i == S        -> 0
      |- dist[i] == INF -> NoPath
      `- 否则           -> dist[i]