吃奶酪

形式化题目

平面上有 $n$ 个点（奶酪）和一个固定起点 $O=(0,0)$ 。一只老鼠要从 $O$ 出发，依次经过每个点（每个点访问一次），求路径总长度的最小值。两点间的距离为欧氏距离 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 。

本质是起点固定、终点不限的最短 Hamilton 路径问题，即 TSP（旅行商问题）的"终点不限"变体：不需要回到起点。

思路

先看一个可以直接验证想法的朴素解：

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/**
 * 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-08-13 13:20
 * update_at: 2026-08-13 13:20
 */
// brute.cpp：小数据暴力解，把“下一块吃哪块奶酪”看成选择序列来递归枚举所有吃奶酪顺序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16;
const double INF = 1e100;

int n;
double x[MAXN], y[MAXN];      // 每块奶酪的坐标
int path[MAXN];               // path[dep]：第 dep 步吃的奶酪编号，组成完整吃奶酪顺序
bool used[MAXN];              // used[i]：第 i 块奶酪是否已经吃过
double ans;                   // 记录当前找到的最短总距离

// 两点之间的欧氏距离。
double dist(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}

// 一条完整吃奶酪顺序已经生成，按顺序把距离累加起来。
double calc_answer() {
    double cur = dist(0, 0, x[path[1]], y[path[1]]);   // 从原点出发
    for (int i = 2; i <= n; i++) {
        cur += dist(x[path[i - 1]], y[path[i - 1]], x[path[i]], y[path[i]]);
    }
    return cur;
}

// 第 dep 层在做“选择”：从没吃过的奶酪里选一块作为第 dep 步的目标。
void dfs(int dep) {
    if (dep == n + 1) {
        // 一条完整顺序生成完毕，统一检查并统计答案
        ans = min(ans, calc_answer());
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        path[dep] = i;
        dfs(dep + 1);
        used[i] = false;   // 回溯，恢复状态
    }
}

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

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

    ans = INF;
    dfs(1);

    cout.setf(ios::fixed);
    cout << setprecision(2) << ans << '\n';
    return 0;
}

brute.cpp 把"吃奶酪"看成一条选择序列：dfs(dep) 的每一层从没吃过的奶酪里选一块填进 path[dep]，dep == n + 1 时一条完整顺序生成完毕，在叶子节点调用 calc_answer() 按顺序累加距离。所有 $n!$ 种顺序都会被枚举到，结果一定正确，但 $15! \approx 1.3 \times 10^{12}$ 种顺序不可能跑完。

关键观察："已经吃了哪些奶酪 + 最后停在哪块"两个信息，就完全决定了未来怎么走。起点固定、每块最多吃一次，先吃谁后吃谁的历史并不影响后续决策。于是把"完整顺序"压缩成状态：

dp[mask][u] = \text{已吃集合为 } mask \text{ 且最后停在 } u \text{ 的最短距离}

转移：从 dp[mask][u] 走向一块还没吃的奶酪 v，用 $dis[u][v]$ （预处理好的距离）更新 dp[mask | (1<<(v-1))][v]。初始状态 dp[1<<(i-1)][i] = dis0[i] 表示从原点直接走到第 $i$ 块奶酪；答案取 dp[(1<<n)-1][i] 的最小值——不要求回原点，所以不再补一段回程。

DP 转移表

这张表展示 2 块奶酪 A=(1,0)、B=(0,1) 时的全部状态。mask 用两位二进制表示已吃集合，单元格是"最后停在对应奶酪时的最短距离"：

`mask`	已吃集合	最后在 A	最后在 B
`01`	只有 A	1（从原点来）	不可达
`10`	只有 B	不可达	1（从原点来）
`11`	A 和 B	$1+\sqrt2$ ，由 `10` 停在 B 时走来	$1+\sqrt2$ ，由 `01` 停在 A 时走来

先看前两行：初始状态只能是从原点直接走到某一块，dp[01][A] = 1、dp[10][B] = 1。再看最后一行：dp[11][A] 只能从 dp[10][B]（已吃 B、停在 B）加 $dis[B][A] = \sqrt{2}$ 走来，dp[11][B] 只能从 dp[01][A] 走来，所以两个单元格都等于 $1 + \sqrt{2}$ 。观察要点：同一个已吃集合必须区分"最后在哪一块"，因为下一次移动的起点不同；最后一行两个来源都被取到，答案就是这一行的最小值（终点不限，不回原点）。

代码

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/**
 * 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-08-13 13:20
 * update_at: 2026-08-13 13:20
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16;        // n <= 15，数组下标从 1 开始
const double INF = 1e100;   // 足够大的数，作为“不可达”

int n;
double x[MAXN], y[MAXN];         // 每块奶酪的坐标，从 1 开始编号
double dis0[MAXN];               // dis0[i]：原点到第 i 块奶酪的距离
double dis[MAXN][MAXN];          // dis[i][j]：第 i 块到第 j 块奶酪的距离
double dp[1 << 15][MAXN];        // dp[mask][u]：已吃集合为 mask 且最后停在 u 的最短距离

// 两点之间的欧氏距离。
double dist(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}

void solve() {
    int full = 1 << n;

    // 先把所有状态初始化为不可达
    for (int mask = 0; mask < full; mask++) {
        for (int i = 1; i <= n; i++) {
            dp[mask][i] = INF;
        }
    }

    // 初始状态：从原点 (0,0) 直接走到第 i 块奶酪
    for (int i = 1; i <= n; i++) {
        dp[1 << (i - 1)][i] = dis0[i];
    }

    // 状态转移：从 dp[mask][u] 走向还没吃的奶酪 v
    for (int mask = 0; mask < full; mask++) {
        for (int u = 1; u <= n; u++) {
            if (dp[mask][u] >= INF / 2) {
                continue;   // 该状态不可达
            }
            for (int v = 1; v <= n; v++) {
                if (mask & (1 << (v - 1))) {
                    continue;   // v 已经吃过了
                }
                int nmask = mask | (1 << (v - 1));
                dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + dis[u][v]);
            }
        }
    }

    // 答案：吃完全部奶酪（mask = full-1）后，最后停在哪一块都行
    double ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, dp[full - 1][i]);
    }

    cout.setf(ios::fixed);
    cout << setprecision(2) << ans << '\n';
}

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

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

    // 预处理距离：原点到每块奶酪、任意两块奶酪之间
    for (int i = 1; i <= n; i++) {
        dis0[i] = dist(0, 0, x[i], y[i]);
        for (int j = 1; j <= n; j++) {
            dis[i][j] = dist(x[i], y[i], x[j], y[j]);
        }
    }

    solve();

    return 0;
}

复杂度

时间：状态数 $n \cdot 2^n$ ，每个状态枚举下一点 $O(n)$ ，预处理距离 $O(n^2)$ ，总 $O(n^2 2^n)$ 。
空间： $dp$ 数组大小 $2^n \times n$ ， $O(n 2^n)$ 。

总结

这题是状态压缩 DP 最标准的入门模型： $n \leqslant 15$ 提示可以用 mask 压集合，dp[mask][u] 的"集合 + 最后位置"状态直接对应 TSP。和标准 TSP 模板相比只有两处小改动：初始化用原点到各点的距离（起点固定），答案取全集行的最小值（终点不限，不加回程）。rbook 的《状态压缩 DP》讲解的就是这个模型，其模板 bitmask-dp-tsp 与本解的转移结构一致；暴力枚举部分参考了《全排列》的 permutation 模板。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20朴素枚举（brute.cpp）
  选择序列：第 1 步吃哪块、第 2 步吃哪块 ...
  叶子节点按顺序累加距离            n! 种顺序
        |
        | 瓶颈：15! ≈ 1.3e12 种顺序，无法枚举
        v
关键观察
  已吃集合 mask + 最后停在 u 完全决定未来怎么走
  （起点固定、每块最多访问一次，路径历史无影响）
        |
        v
状态压缩 DP（main.cpp）
  dp[mask][u] = 已吃集合为 mask、最后停在 u 的最短距离
  预处理 dis0[i]（原点距离）、dis[i][j]（两点距离）
  初始化 dp[1<<(i-1)][i] = dis0[i]
  转移 dp[mask|(1<<(v-1))][v] = min(..., dp[mask][u] + dis[u][v])
  答案 min(dp[(1<<n)-1][i])，不回原点
        |
        v
复杂度 O(n^2 * 2^n)，空间 O(n * 2^n)

观察要点：图的上半段是暴力在哪里慢——完整顺序数是指数级之上的阶乘级；中间的关键观察把"完整顺序"压缩成"集合 + 最后位置"两个字段；下半段就是标准 TSP 状压转移，整道题的难点其实只有初始化和答案统计这两个"起点固定、终点不限"的细节。

目录

形式化题目

思路

DP 转移表

代码

复杂度

总结

图示解析