【例9.5】城市交通网络

题目描述

有 $N$ （ $N \leqslant 20$ ）个城市，单向路网中所有道路都从编号小的城市通向编号大的城市。给出 $N \times N$ 的费用矩阵 $w_{i,j}$ （0 表示两点间没有直通道路），求城市 1 到城市 $N$ 的最小总费用及经过的城市序列。输入第一行一个整数 $N$ ，随后 $N$ 行每行 $N$ 个数构成费用矩阵；输出两行，第一行 minlong=最小费用，第二行是路径上依次经过的城市编号（空格分隔）。样例：输入 10 及 10×10 矩阵（ $w_{1,2}=2,\ w_{1,3}=5,\ w_{1,4}=1,\ w_{3,5}=6,\ w_{5,8}=3,\ w_{8,10}=5$ 等），输出 minlong=19 与 1 3 5 8 10。

思路

所有边都从小编号指向大编号，编号本身就是拓扑序，于是从 $N-1$ 倒推到 1 做逆拓扑序 DP： $f(N)=0$ ， $f(i)=\min\limits_{w_{i,j}\neq 0}\bigl(w_{i,j}+f(j)\bigr)$ ，其中 $f(i)$ 表示从 $i$ 到 $N$ 的最小费用。用 go[i] 记下取得最小值的后继，答案 $f(1)$ ，再从 1 沿 go 回溯即得路径。总转移次数 $O(N^2)$ 。

参考代码

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#!/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-09-30 02:17
# update_at: 2026-09-30 02:17

import sys

INF = 10000005  # 不可达哨兵：费用非负、规模极小，真实答案到不了这个量级


def shortest(cost: list[list[int]]) -> tuple[int, list[int]]:
    """逆序 DAG 最短路 DP，返回 (从 1 到 n 的最短费用, 最短路径上的城市序列)。

    边只从编号小的城市指向编号大的城市（与配图中 A→E 的方向一致），
    所以从 n-1 倒着推到 0 时，所有后继的最优值都已算好——这正是逆拓扑序。
    f[i] 记「从 i 到终点 n 的最短费用」，go[i] 记最短路上 i 的下一站。
    """
    n = len(cost)
    f: list[int] = [INF] * n
    go: list[int] = [0] * n  # 下一站的城市编号（1 起），0 表示不可达或已是终点
    f[n - 1] = 0  # 终点到自身的费用为 0

    for i in range(n - 2, -1, -1):
        best, nxt = f[i], 0  # 保留 "没有更优后继" 的初值，回溯时靠 go=0 停止
        for j in range(i + 1, n):
            w = cost[i][j]
            if w and w + f[j] < best:  # 费用为 0 表示没有直通边；严格小于让平手时保序
                best, nxt = w + f[j], j + 1
        f[i], go[i] = best, nxt

    # 从 1 号城市沿 go 逐跳回溯，到终点（go 为 0）自然停下
    path: list[int] = [1]
    k = go[0]
    while k:
        path.append(k)
        k = go[k - 1]
    return f[0], path


def solve() -> None:
    nums = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(nums)  # 城市数量
    # N×N 费用矩阵：cost[i][j] 是 i→j 的直通费用，0 表示两点间没有直通边
    cost = [[next(nums) for _ in range(n)] for _ in range(n)]

    total, path = shortest(cost)
    print(f"minlong={total}")
    print(*path)


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/**
 * 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 07:19
 * update_at: 2026-10-05 07:19
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 25;
const ll INF = 1000000000000000000LL;

int n;                 // 城市数量
ll w[MAXN][MAXN];      // w[i][j]：城市 i 直达城市 j 的费用，0 表示没有直通边
ll f[MAXN];            // f[i]：从城市 i 到城市 n 的最小费用
int go[MAXN];          // go[i]：最优路线上从城市 i 出发的下一站，0 表示终点或不可达

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> w[i][j];
        }
    }

    // 所有边都是小编号指向大编号，编号即拓扑序，从 n 倒着推就是逆拓扑序 DP
    for (int i = 1; i <= n; i++) {
        f[i] = INF;
    }
    f[n] = 0;

    for (int i = n - 1; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) {
            if (w[i][j] != 0 && w[i][j] + f[j] < f[i]) {
                f[i] = w[i][j] + f[j];
                go[i] = j;
            }
        }
    }

    cout << "minlong=" << f[1] << "\n";

    // 从城市 1 沿 go 逐跳回溯到 n，输出路径上的城市编号
    int cur = 1;
    cout << cur;
    while (go[cur] != 0) {
        cur = go[cur];
        cout << " " << cur;
    }
    cout << "\n";

    return 0;
}