最短路径(shopth)

形式化题目

给定一个包含 $n$ 个顶点的有向图 $G = (V, E)$ ，顶点编号从 $1$ 到 $n$ ，并给定源点 $v_0$ 。图以邻接矩阵的形式给出，矩阵中 - 表示没有直接连接的边，非 - 元素表示边的权值。权值可能存在负数，但保证图中的所有的有向环权值和都是正的（即不存在负权环）。要求计算从源点 $v_0$ 到图 $G$ 中其他所有顶点的最短路径长度，并按顶点编号从小到大的顺序输出。

数据范围： $2 \le n \le 80$ 。边权极大（例如可能达到 $1.5 \times 10^{12}$ ），可能会超过 32 位整数的表示范围。

正解

思路

本题为单源最短路径（SSSP）问题。因为图中的边权可能为负数，因此不能使用无法处理负权边的 Dijkstra 算法。题目明确保证了所有的有向环权值和都是正的（即不存在负权环），我们可以直接使用 Bellman-Ford 算法。对于 $n \le 80$ 的数据规模，邻接矩阵和 $O(n^3)$ 的复杂度非常快且不容易出错。

算法步骤：

安全且鲁棒的读入：
- 数据中存在远超 32 位整数范围的极大权值，并且存在表示不连通的占位符 -。
- 数据极其坑人：某个测试点中的某一行数据在行尾 缺失了 1 个元素。如果按照整个文件分割 token 连续读入，会导致后面的数据全部提前一个位置读入（即发生了整个矩阵元素的错位），引发越界甚至在最后一轮读空时崩溃。因此，必须按行读入矩阵。读取每行并分割其自身的 token，如果缺失元素，缺失的部分自然会被视作 - (无边)，且绝不会影响后续行的读入。
初始化：定义数组 dist，将源点 source 的距离设为 0，其余点设为极大值（例如 $10^{18}$ 避免与负权相加产生下溢）。
松弛操作：最多执行 $n-1$ 轮迭代。每轮遍历邻接矩阵中的所有存在且从源点可达的边 $(i, j)$ ，如果 dist[i] + adj[i][j] < dist[j]，则更新 dist[j]。如果某一轮中没有任何顶点被更新，说明已经达到了最短路，可以提前跳出。
输出结果：按题目要求的格式 (s -> i) = d 输出除了源点外的所有顶点的最短距离。

代码

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#!/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-10-08 16:42
# update_at: 2026-10-08 16:42

import sys

INF = 10**18  # 无穷大：足够大，且与边权相加不会溢出

type Matrix = list[list[int | None]]  # 邻接矩阵，None 表示无边


def read_matrix(n: int, rows: list[str]) -> Matrix:
    """按行读入邻接矩阵：'-' 记为 None（无边），对角线上的 0 保留但自环不影响最短路。

    必须按行读、不能把整个文件 split() 成 token 连读：数据文件 SHOPTH8.IN 的
    第 10 行只有 19 个 token（n=20），连读会让后面所有行整体错位；按行读时
    短行只影响自己这一行，不足的列按无边处理。
    """
    adj: Matrix = [[None] * (n + 1) for _ in range(n + 1)]
    for i, row in enumerate(rows[:n], 1):
        for j, token in enumerate(row.split(), 1):
            if j > n:                      # 行内 token 多于 n 个（脏行）时只取前 n 个
                break
            if token != '-':
                adj[i][j] = int(token)
    return adj


def shortest(n: int, source: int, adj: Matrix) -> list[int]:
    """Bellman-Ford：无负环时松弛 n-1 轮足够，返回 dist[1..n]。

    有负边所以不能用 Dijkstra；题面保证所有有向环权值和为正，即无负环。
    """
    dist = [INF] * (n + 1)
    dist[source] = 0
    for _ in range(n - 1):
        changed = False                    # 本轮没有变短就已收敛，提前退出
        for i in range(1, n + 1):
            if dist[i] == INF:
                continue
            for j in range(1, n + 1):
                w = adj[i][j]
                if w is None:
                    continue
                cand = dist[i] + w         # 用 i 中转一次的距离
                if cand < dist[j]:
                    dist[j] = cand
                    changed = True
        if not changed:
            break
    return dist


def solve() -> None:
    data = iter(sys.stdin.read().splitlines())
    n = int(next(data))                    # 顶点数
    source = int(next(data))               # 源点
    rows = [next(data) for _ in range(n)]
    dist = shortest(n, source, read_matrix(n, rows))
    print('\n'.join(f"({source} -> {i}) = {dist[i]}"
                    for i in range(1, n + 1) if i != source))


if __name__ == "__main__":
    solve()

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/**
 * 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-08 16:38
 * update_at: 2026-10-08 16:46
 */
// 一本通 1378《最短路径(shopth)》：有向图含负边（无负环），求单源最短路。
// 有负边 ⇒ 用 Bellman-Ford，无负环时松弛 n-1 轮足够。
// 读入必须“按行”读矩阵：数据文件 SHOPTH8.IN 第 10 行少了 1 个 token，
// 按 token 连读会把后续所有行整体错位（顺便把最后一轮读空导致 stoll 崩溃）。
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

typedef long long ll;

const int MAXN = 85;    // n <= 80
const ll INF = 1e18;    // 无穷大：足够大，且与边权相加不会溢出

ll adj[MAXN][MAXN];     // adj[i][j] = 边 i->j 的权；INF 表示 i 到 j 无边
ll dist[MAXN];          // dist[i] = 源点到 i 的最短距离

void solve() {
    int n;
    if (!(cin >> n)) return;
    int source;
    cin >> source;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            adj[i][j] = INF;
        }
    }

    // 逐行读邻接矩阵：一行给出一行边权，'-' 表示无边。
    // 行内 token 少一个也只影响本行，不会污染后面的行。
    string line;
    getline(cin, line);                 // 吃掉源点那行剩下的换行
    for (int i = 1; i <= n; i++) {
        getline(cin, line);
        istringstream tokens(line);
        for (int j = 1; j <= n; j++) {
            string token;
            if (!(tokens >> token)) break;   // 本行 token 不足，剩下的列保持无边
            if (token != "-") {
                adj[i][j] = stoll(token);
            }
        }
    }

    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[source] = 0;

    // Bellman-Ford：每轮扫描所有边做一次松弛，最多 n-1 轮
    for (int round = 1; round < n; round++) {
        bool changed = false;           // 本轮没有任何距离变短就提前收敛
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) continue;
            for (int j = 1; j <= n; j++) {
                if (adj[i][j] == INF) continue;
                ll cand = dist[i] + adj[i][j];
                if (cand < dist[j]) {
                    dist[j] = cand;
                    changed = true;
                }
            }
        }
        if (!changed) break;
    }

    for (int i = 1; i <= n; i++) {
        if (i == source) continue;
        cout << "(" << source << " -> " << i << ") = " << dist[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

时间复杂度：建图复杂度为 $O(n^2)$ 。Bellman-Ford 算法最多执行 $n-1$ 轮，每轮需要遍历整个 $n \times n$ 邻接矩阵耗时 $O(n^2)$ ，因此总时间复杂度为 $O(n^3)$ （或 $O(n \cdot m)$ ）。由于 $n \le 80$ ，运算量最大约 $5 \times 10^5$ ，执行极快。
空间复杂度：需要存储邻接矩阵和一维距离数组，空间复杂度为 $O(n^2)$ 。

总结

含有负边权的最短路：图中若有负边，绝不能使用 Dijkstra。题目保证没有负权环时，使用 Bellman-Ford 或 SPFA，最多松弛 $n-1$ 轮即可。
按行读入的鲁棒性（本题最大的坑）：测试数据 SHOPTH8.IN 是一组“脏数据”，其第 10 行的数据缺少了最后 1 个元素。如果用 C++ 的 cin >> token 或 Python 的 f.read().split() 将整个文件当做 token 流一口气读入，缺少的这 1 个元素会导致其后所有行的读取发生整体错位，并在读取最后一行时因超出边界抛出异常崩溃。而按行读取（C++ 的 getline 结合 istringstream，Python 的 splitlines 分行解析）即使遇到了元素缺失，也只会影响当前行的最后几列，绝不会污染后续其他行，具有极好的工程鲁棒性。
未定义的不可达点输出：题目并没有规定如果某些点不可达应该输出什么。在官方数据的 10 个测试点中，所有点相对于源点实际上全部可达。现有代码直接保留无穷大标志 1e18，这是由我们约定的处理方式，而不是数据支持和要求的结论。
素材陷阱：在测试过程中发现，附带的 std.cpp 使用了 scanf 读取并且对 - 处理有 Bug（无法成功回退或处理字符），导致在面对所有测试点时都会产生读入错误，输出全部不对。请以 cin/istringstream 和 Python 的字符串解析为准。
输出格式：注意输出 (s -> i) = d 时各个部分之间的空格，不要打印源点到自身的距离，并且需按照顶点编号 $i$ 升序输出。对角线上的 $0$ 或负数被当做权值为 0 或对应的自环即可，并不影响最短路径逻辑。

目录

形式化题目

正解

思路

代码

复杂度

总结