前言：
许多算法的状态数并不支持其在多项式时间内运行完成。比如TSP问题这种大部分为NP-Hard的问题。
在数据范围缩小的前提下（例如\(n\leq 21\)），不妨将状态数压缩成二进制情况，用一串二进制数表示整体情况。
洛谷 P1433
记\(dp_{k,i}\)为：当前整体状态为\(k\)，老鼠走到了第\(i\)个奶酪的最短距离。
其中\(k\)是一串二进制数字，例如01011010表示经过了第2、4、5、7个奶酪（从右往左计数）。
易得状态转移方程为：
\[dp_{k,i}=min\{dp_{k-[1<<(i-1)],j}+dis(j,i)\}(1\leq i,j\leq n) \]其中:
1<<(i-1)表示第\(i\)位状态，
k-[1<<(i-1)表示没有经过第\(i\)位时的整体状态,
dp_{k-[1<<(i-1)], j} 表示在第\(j\)个点且没有经过第\(i\)位的最短距离。
最后对以每个点为结尾的满状态（n个点均经过）dp方程取最小值即可。
注：注意位运算优先级，debug了很久才发现
Code:
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
const int maxn = 15 + 5;
double dis[maxn][maxn];//i到j的距离
double dp[40000][maxn];//二进制状态为i,目前在第j个奶酪处
double ans = 114514.0, x[maxn], y[maxn];
int n;
double d(int a, int b) {
return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
int main() {
scanf("%d", &n);
memset(dp, 127, sizeof(dp));
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &x[i], &y[i]);
for (int i = 0; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
dis[i][j] = dis[j][i] = d(i, j);
}
}
for (int i = 1; i <= n; i++)
dp[1 << (i - 1)][i] = dis[i][0];//初始化第i个点的距离即为与原点的距离
for (int k = 1; k < (1 << n); k++)//枚举每种状态
for (int i = 1; i <= n; i++) {
if ((k & (1 << (i - 1))) == 0) continue;//第i位为0
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if ((k & (1 << (j - 1))) == 0) continue;//第j位为0
dp[k][i] = std::min(dp[k][i], dp[k - (1 << (i - 1))][j] + dis[j][i]);
}
}
for (int i = 1; i <= n; i++)
ans = std::min(ans, dp[(1 << n) - 1][i]);//更新以第i个奶酪为结尾的n个满状态答案
printf("%.2lf", ans);
return 0;
}