【题目来源】
洛谷：P1433 吃奶酪 - 洛谷
【题目描述】
房间里放着 \(n\) 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 \((0,0)\) 点处。
【输入】
第一行有一个整数，表示奶酪的数量 \(n\)。
第 \(2\) 到第 \((n+1)\) 行，每行两个实数，第 \((i+1)\) 行的实数分别表示第 \(i\) 块奶酪的横纵坐标 \(x_i,y_i\)。
【输出】
输出一行一个实数，表示要跑的最少距离，保留 \(2\) 位小数。
【输入样例】
4
1 1
1 -1
-1 1
-1 -1
【输出样例】
7.41
【解题思路】
【算法标签】
《洛谷 P1433 吃奶酪》 #动态规划,dp# #状态压缩#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义点结构体
struct point
{double x, y; // 点的坐标bool visit; // 是否已访问int num; // 点的编号
} ps[16]; // 最多15个点（编号0-15）int n; // 点的数量
double ans = DBL_MAX; // 存储最短路径长度，初始为最大值
double f[16][33000] = {0}; // 记忆化数组，f[i][j]表示状态j下到达点i的最短距离/*** 计算两点间距离* @param p1 第一个点* @param p2 第二个点* @return 两点间距离*/
double dis(point p1, point p2)
{return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}/*** 深度优先搜索函数* @param p 当前点* @param step 已访问的点数* @param mark 状态标记（二进制位表示已访问的点）* @param s 当前路径长度*/
void dfs(point p, int step, int mark, double s)
{// 所有点都已访问，更新最短路径if (step == n){if (ans > s){ans = s;}return;}// 尝试访问每个未访问的点for (int i = 0; i < n; i++){if (ps[i].visit){continue;}int tmp = mark + (1 << i); // 更新状态标记// 如果新状态更优，则继续搜索if (f[i][tmp] == 0 || f[i][tmp] > f[p.num][mark] + dis(ps[i], p)){f[i][tmp] = f[p.num][mark] + dis(ps[i], p);ps[i].visit = 1; // 标记为已访问dfs(ps[i], step + 1, tmp, s + dis(ps[i], p));ps[i].visit = 0; // 回溯，恢复未访问状态}}
}int main()
{cin >> n; // 输入点的数量// 输入每个点的坐标并初始化for (int i = 0; i < n; i++){cin >> ps[i].x >> ps[i].y;ps[i].visit = 0;ps[i].num = i;}// 创建起点（原点），并标记为已访问point p = {0, 0, 1, 0};// 开始深度优先搜索dfs(p, 0, 0, 0);// 输出最短路径长度，保留两位小数printf("%.2f", ans);return 0;
}
【运行结果】
4
1 1
1 -1
-1 1
-1 -1
7.41