题目
洛谷在这道题中，有一个说明：2022.7.13：新增加一组Hack数据。我不知道这个是什么意思，不过我大概能知道：本来这道题可以用DFS解决，但现在不行：会有三个超时。
分析
要点一：路线分析
老鼠的路线并不遵循DP中常见的“往右往下”——因此转移方程比较简单——的规律。理论上，从老鼠出发点(0, 0)开始不重复地走遍其他N个点，一共有\(N!\)种走法。我们要找的，是这\(N!\)种走法中（以某个点i）结束的路径中最短的那条。
这里有了解题的第一个要点：所有的最后状态都必须是全部遍历，所以不能用这个状态本身作为判定的标准，还必须加上最后的终点。所以，声明的状态数组应该类似dp[status][point]这样的。而且我们最后要对处于最终status的所有point进行遍历，比较所有的距离。
要点二：状态、最终状态和表示
那么什么是最终状态？“吃掉所有奶酪”=“访问了所有的点”=“所有点的位置标1”=“1111111...11”（N个1）。
这里有了解题的第二个要点：这N个点访问的状态一共是\(2^N\)种不同的排列，用二进制位+排列组合方式最合理。于是我们可以遍历所有的状态，并进行相应的转移。
要点三：转移的考量
那么如何进行状态转移呢？这个不算太复杂。
假定我们有N个数字，目前前面4个点的状态是1010，表示用了第1和第3个位置，那么理论上，第5个位置可以是任意点，但有两个重要的例外：
- 当前状态下，已经用掉了第5点（也就是重复之前的点）。比如：
1-0-3-0-(3)就是不对的——要剪枝。 - 不能转移到和当前“不同”状态。不能从
1010转到11101，但可以到10101（表示连了一个合理的点到第5个位置）。1
看到这里，可能会有疑问：10101里的0怎么办？不用担心，因为我们使用全排列的方式进行操作，所以早晚会找到所有的状态的。
转移方程为：
int new_s = s | (1 << (j - 1)); //合法的j点，要更新状态，用位处理。
dp[new_s][j] = min(dp[new_s][j], dp[s][i] + dist[i][j]);上述第三点很重要，我们现在用DP而不是DFS。用DFS可以保证从前一个状态转到下一个合法的状态。但DP中，我们对每个状态都进行了记录，所以要排除掉非法的转移可能。
实际代码采用i/j双循环，再外套一个所有状态的全排列实现，并尽量早剪枝。
答案
思考
这道题似乎也可以用枚举的方式进行，因为根据题意，\(1\le n\le 15\)，而15!不算太大。但是，实际操作中还是超时。我将代码附上，可以作为一个在时间限制没有那么严格的前提下，更容易理解的解法。
double dist[MAXN][MAXN]; // 预处理距离
double getDistance(double x1, double y1, double x2, double y2)
{
// ...
}
int main()
{
// ...
// 预处理所有点对之间的距离，包括起点(0,0)
// 存放在dist[i][j]中，表示i点到j点的距离
// ...
double min_dist = 1e9;
do
{
double total = dist[0][path[0]]; // 从起点到第一个点的距离
if (total >= min_dist)
continue; // 第一步就超过最小值，直接跳过
// 计算剩余点的距离
for (int i = 0; i < n - 1; i++)
{
total += dist[path[i]][path[i + 1]];
if (total >= min_dist)
{
break; // 提前剪枝
}
}
min_dist = min(min_dist, total);
} while (next_permutation(path.begin(), path.end()));
// path中就简单存放第`i`个的索引（也就是1-n。这样可以通过next_permutation生成全排列，然后获得dist。）
}-
这里为了说明方便，采用的说明方式和最后编程采用的表示方式是不同的。但不影响理解。 ↩