「一本通 3.2 练习 4」新年好

形式化题目

给定一个含 $n$ 个节点、 $m$ 条边的连通无向正权图 $G = (V, E)$ 。给定节点 $1$ 作为起点，以及 $5$ 个目标节点 $a, b, c, d, e$ 。要求找到一个从节点 $1$ 出发、按某种次序遍历全部 $5$ 个目标节点的路径序列 $1 \to p_1 \to p_2 \to p_3 \to p_4 \to p_5$ （其中 $(p_1, \dots, p_5)$ 为 $(a, b, c, d, e)$ 的全排列），最小化该序列对应的总路径长度：

\operatorname{dist}(1, p_1) + \sum_{i=1}^{4} \operatorname{dist}(p_i, p_{i+1})

样例示意

graph LR
    1((1:佳佳家)) ---|8| 2((2:亲戚a))
    1 ---|7| 6((6:亲戚e))
    2 ---|3| 3((3:亲戚b))
    3 ---|4| 4((4:亲戚c))
    4 ---|5| 5((5:亲戚d))
    5 ---|2| 6

样例中，亲戚所在车站依次为 $2, 3, 4, 5, 6$ 。若选择拜访次序 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ ：

$1 \to 2$ ：用时 $8$
$2 \to 3$ ：用时 $3$
$3 \to 4$ ：用时 $4$
$4 \to 5$ ：用时 $5$
$5 \to 6$ ：用时 $2$ 总用时为 $8 + 3 + 4 + 5 + 2 = 22$ 。

若选择次序 $1 \to 6 \to 5 \to 4 \to 3 \to 2$ ：

$1 \to 6$ ：用时 $7$
$6 \to 5$ ：用时 $2$
$5 \to 4$ ：用时 $5$
$4 \to 3$ ：用时 $4$
$3 \to 2$ ：用时 $3$ 总用时为 $7 + 2 + 5 + 4 + 3 = 21$ 。为全局最优解。

正解

思路

本题核心在于观察到关键节点极少：

出发点固定为车站 $1$ 。
目标拜访的亲戚车站只有 $5$ 个（ $a, b, c, d, e$ ）。

尽管全图规模较大（ $n \leqslant 50000$ ， $m \leqslant 10^5$ ），但亲戚之间的拜访顺序只有 $5! = 120$ 种可能。

对于任意一种拜访顺序，例如 $1 \to p_1 \to p_2 \to p_3 \to p_4 \to p_5$ ，中途每一段（例如从 $p_i$ 走到 $p_{i+1}$ ）的最佳走法必然是图上两点之间的最短路。因此，我们只需要知道这 $6$ 个关键点之间两两的最短路距离。

算法步骤：

将车站 $1$ 和 $5$ 个亲戚所在的车站按顺序编号为 $0, 1, 2, 3, 4, 5$ 。
以这 $6$ 个节点分别作为单源起点，各执行一次堆优化 Dijkstra 算法，共执行 $6$ 次。
提取它们两两之间的最短距离，构建一张 $6 \times 6$ 的距离矩阵。
使用全排列枚举亲戚的 $120$ 种拜访次序，累加各段的最短路长度并取最小值。

代码

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#!/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-04-18 10:00
# update_at: 2026-04-18 10:00

import heapq
import itertools
import sys

INF = 10**18


def dijkstra(n: int, adj: list[list[tuple[int, int]]], start: int) -> list[int]:
    """计算从源点 start 出发到达所有顶点的单源最短路距离数组。"""
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            new_d = d + w
            if new_d < dist[v]:
                dist[v] = new_d
                heapq.heappush(pq, (new_d, v))

    return dist


def min_visit_time(key_nodes: list[int], dist_map: list[list[int]]) -> int:
    """枚举拜访 5 个亲戚的所有排列顺序，计算从家 (0) 出发拜访全部亲戚的最短总时间。"""
    return min(
        dist_map[0][order[0]]
        + sum(dist_map[order[i]][order[i + 1]] for i in range(4))
        for order in itertools.permutations(range(1, 6))
    )


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        n_token = next(data)
    except StopIteration:
        return
    n, m = int(n_token), int(next(data))
    relatives = [int(next(data)) for _ in range(5)]

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

    # 关键节点：0 号为佳佳家（车站 1），1..5 号为五个亲戚所在车站
    key_nodes = [1] + relatives
    all_dist = [dijkstra(n, adj, s) for s in key_nodes]
    dist_map = [[all_dist[i][key_nodes[j]] for j in range(6)] for i in range(6)]

    ans = min_visit_time(key_nodes, dist_map)
    print(ans)


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/**
 * 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 04:41
 * update_at: 2026-10-05 04:41
 */
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

const ll MAXN = 50005;   // 车站数上限
const ll MAXM = 100005;  // 公路数上限
const ll INF = 1e18;

// 链式前向星存图（无向图，双向加边）
ll head[MAXN];  // head[u] = u 点的第一条边编号
ll nxt[MAXM * 2];  // 同一起点下一条边
ll to_v[MAXM * 2];  // 边的终点
ll weight[MAXM * 2];  // 边权（时间）
ll cnt_edge = 0;

ll n, m;
ll key_node[6];  // key_node[0] = 家(车站1)，key_node[1..5] = 五个亲戚的车站
ll dist[6][MAXN];  // dist[k][u] = 从第 k 个关键点出发到 u 的最短路
ll d[6][6];  // d[i][j] = 关键点 i 到关键点 j 的最短路距离（6x6 距离矩阵）

// 加一条有向边
void add_edge(ll u, ll v, ll w) {
    cnt_edge++;
    to_v[cnt_edge] = v;
    weight[cnt_edge] = w;
    nxt[cnt_edge] = head[u];
    head[u] = cnt_edge;
}

// 堆优化 Dijkstra：以 key_node[k] 为源点求单源最短路
void dijkstra(ll k) {
    for (ll i = 1; i <= n; i++) dist[k][i] = INF;
    ll s = key_node[k];
    dist[k][s] = 0;
    // 小根堆：pair(当前距离, 点编号)
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        pair<ll, ll> top = pq.top();
        pq.pop();
        ll d = top.first;
        ll u = top.second;
        if (d > dist[k][u]) continue;  // 过期状态，跳过
        for (ll e = head[u]; e; e = nxt[e]) {
            ll v = to_v[e];
            ll nd = d + weight[e];
            if (nd < dist[k][v]) {
                dist[k][v] = nd;
                pq.push(make_pair(nd, v));
            }
        }
    }
}

// 全排列枚举 5 个亲戚（关键点 1..5）的拜访顺序
// perm[p] = 第 p 站拜访的关键点编号
ll perm[6];
bool used[6];
ll ans = INF;

// 当前已确定前 pos 站，sum 为从家出发走到上一站的总距离
void dfs_choose(ll pos, ll last, ll sum) {
    if (pos == 6) {  // 5 个亲戚全部拜访完
        if (sum < ans) ans = sum;
        return;
    }
    // 这一层在选择：第 pos 站拜访哪个还没去过的亲戚
    for (ll k = 1; k <= 5; k++) {
        if (used[k]) continue;
        used[k] = true;
        perm[pos] = k;
        dfs_choose(pos + 1, k, sum + d[last][k]);
        used[k] = false;
    }
}

int main() {
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= 5; i++) scanf("%lld", &key_node[i]);
    key_node[0] = 1;  // 佳佳家在车站 1

    memset(head, 0, sizeof(head));
    for (ll i = 1; i <= m; i++) {
        ll x, y, t;
        scanf("%lld %lld %lld", &x, &y, &t);
        add_edge(x, y, t);
        add_edge(y, x, t);
    }

    // 6 个关键点各跑一次堆优化 Dijkstra，提取两两最短路得到距离矩阵
    for (ll k = 0; k <= 5; k++) dijkstra(k);
    for (ll i = 0; i <= 5; i++)
        for (ll j = 0; j <= 5; j++)
            d[i][j] = dist[i][key_node[j]];

    dfs_choose(1, 0, 0);
    printf("%lld\n", ans);
    return 0;
}

复杂度

时间复杂度：
- 单次堆优化 Dijkstra 的时间复杂度为 $O((n + m) \log n)$ 。
- 共执行 $6$ 次 Dijkstra，耗时为 $O(6(n + m) \log n)$ 。
- 枚举 $5$ 个亲戚的拜访顺序共有 $5! = 120$ 种，计算每种顺序耗费 $O(1)$ 。
- 综上，总时间复杂度为 $O((n + m) \log n)$ ，在给定范围下可在时限内轻松通过。
空间复杂度：
- 邻接表需要存储 $m$ 条双向边（ $2m$ 条有向边），空间为 $O(n + m)$ 。
- 距离数组与优先队列开销为 $O(n)$ 。
- 距离矩阵与排列规模为 $O(1)$ 。
- 总空间复杂度为 $O(n + m)$ 。

总结

对于“在大型稀疏图上遍历少量特定目标点”的问题，由于目标关键点数量极少，全源最短路算法（如 Floyd）并不适用，而直接从每个关键点各跑一次单源最短路（堆优化 Dijkstra）则是最优雅高效的解法。求出关键点间的距离图后，再结合暴力排列枚举（或状压 DP）即可快速得出最优解。