T11:吃奶酪

解题思路（最短路程吃完所有奶酪）

老鼠从 (0,0) 出发，要把 n 个点（奶酪坐标）全部访问一遍，问最短总路程。不要求回到原点。

这就是经典的 旅行商问题 TSP（从起点出发访问所有点的最短路径），n ≤ 15，可以用 状态压缩 DP 做到 O(n^2·2^n)。

---

状态定义

把奶酪编号 1..n，起点当作编号 0（坐标 (0,0)）。

预处理所有点两两距离 dist[i][j]（含 0..n）。

设：

• dp[mask][i]：从起点 0 出发，已经吃掉集合 mask 中的奶酪（mask 的第 k 位表示奶酪 k 是否吃过），并且最后停在奶酪 i（i 在 1..n）时的最短路程。

---

初始化

只吃一个奶酪 i：

• dp[1<<(i-1)][i] = dist[0][i]

---

状态转移

从上一个停在 j，走到 i：

• dp[mask][i] = min(dp[mask][i], dp[pmask][j] + dista[j][i]);

---

答案

全部吃完时 full = (1<<n)-1，最后可以停在任意一个奶酪点：

ans = min_{i=1..n} dp[full][i]

---

输出格式

题目要求保留 2 位小数。

用 printf("%.2f\n", ans); 或 cout<<fixed<<setprecision(2)。

---

C++ 代码

#include <bits/stdc++.h>                  // 常用头文件
using namespace std;

const int MAXN = 15;                      // n 最大 15
const int MAXS = 1 << MAXN;               // 最大状态数 2^15
const double INF = 1e100;                 // 代表无穷大

double x[MAXN + 1], y[MAXN + 1];          // 点坐标：0 是起点，1..n 是奶酪
double dista[MAXN + 1][MAXN + 1];         // 两点距离表 dista[i][j]
double dp[MAXS][MAXN + 1];                // dp[mask][i]：吃完mask，最后在i的最短路

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

    int n;                                // 奶酪数量
    cin >> n;                             // 输入 n

    x[0] = 0.0;                           // 起点 x
    y[0] = 0.0;                           // 起点 y

    for (int i = 1; i <= n; i++) {        // 读入每块奶酪坐标
        cin >> x[i] >> y[i];              // 第 i 个奶酪 (x[i], y[i])
    }

    for (int i = 0; i <= n; i++) {        // 预处理所有点对距离
        for (int j = 0; j <= n; j++) {
            double dx = x[i] - x[j];      // 横坐标差
            double dy = y[i] - y[j];      // 纵坐标差
            dista[i][j] = sqrt(dx * dx + dy * dy); // 欧式距离
        }
    }

    int full = (1 << n) - 1;              // 全部吃完的状态（二进制全1）

    for (int mask = 0; mask <= full; mask++) {     // 初始化 dp 为 INF
        for (int i = 0; i <= n; i++) {
            dp[mask][i] = INF;
        }
    }

    for (int i = 1; i <= n; i++) {        // 初始化：只吃 i 这一个奶酪
        int mask = 1 << (i - 1);          // mask 的第 (i-1) 位表示奶酪 i
        dp[mask][i] = dista[0][i];        // 从起点 0 直接到 i
    }

    for (int mask = 1; mask <= full; mask++) {     // 枚举所有吃过的集合
        for (int i = 1; i <= n; i++) {             // 枚举最后停在 i
            if (!(mask & (1 << (i - 1)))) continue; // mask 不含 i 就不能停在 i

            int pmask = mask ^ (1 << (i - 1));      // 去掉 i 的上一个集合
            if (pmask == 0) continue;               // 只有一个点的情况已初始化

            for (int j = 1; j <= n; j++) {          // 枚举上一步停在 j
                if (!(pmask & (1 << (j - 1)))) continue; // pmask 必须含 j
                dp[mask][i] = min(dp[mask][i], dp[pmask][j] + dista[j][i]); // 转移
            }
        }
    }

    double ans = INF;                      // 最终答案
    for (int i = 1; i <= n; i++) {         // 最后停在任意 i 都可以
        ans = min(ans, dp[full][i]);       // 取最小
    }

    cout << fixed << setprecision(2) << ans << endl; // 输出保留2位小数
    return 0;                              // 结束
}