AcWing
91. 最短Hamilton路径
状态压缩DP.
假设:一共有七个点，用0，1，2，3，4，5，6来表示，那么先假设终点就是5，在这里我们再假设还没有走到5这个点，且走到的终点是4，那么有以下六种情况：
- first: 0–>1–>2–>3–>4 距离:21
- second: 0–>1–>3–>2–>4 距离:23
- third: 0–>2–>1–>3–>4 距离:17
- fourth: 0–>2–>3–>1–>4 距离:20
- fifth: 0–>3–>1–>2–>4 距离:15
- sixth: 0–>3–>2–>1–>4 距离:18
此时商人显然会走第五种情况，因为每段路程的终点都是4，且每种方案的可供选择的点是0~4，而商人寻求的是走到5这个点的最短距离，而4到5的走法只有一种，所以我们选择第五种方案。可寻找到走到5这个点之前，且终点是4的方案的最短距离，此时0~5的最短距离为(15 + 4走到5的距离)。(假设4–>5 = 8)
同理：假设还没有走到5这个点，且走到的终点是3，那么有一下六种情况:
- first: 0–>1–>2–>4–>3 距离:27
- second: 0–>1–>4–>2–>3 距离:22
- third: 0–>2–>1–>4–>3 距离:19
- fourth: 0–>2–>4–>1–>3 距离:24
- fifth: 0–>4–>1–>2–>3 距离:26
- sixth: 0–>4–>2–>1–>3 距离:17
此时可以做出决定：走第六种方案。此时0~5的最短距离为(17 + 3走到5的距离)。(假设3–>5=5)
由此，我们定义dp数组f[i][j]，表示所有从0走到j,走过的所有点的情况是i的所有路径，的长度最小值。i表示的是一种状态，任意的点是否被走过，用二进制表示，例如，路径经过0，1，2，4这三个点，则i表示为10111.
考虑状态转移方程，假如从终点开始考虑，我们最终要得到的值是f[1111...1][n-1]，可以枚举终点前的一个点，那么f[1111...1][n-1] = min{f[0111...1][j] + w[j][n-1], j∈[0, n-1]且i>>j&1 == 1}，类似地，求f[0111...1][j]…..我们可以从f[0000...1][0]开始递推，枚举每个状态i、路径终点j，并对每个f[i][j]执行状态转移。
状态转移方程可以表示为：
f[i][j] = min{f[i-(1<<j)][k] + w[k][j]}.
算法的时间复杂度：枚举状态$2^n$，枚举终点$n$，枚举转移策略$n$，即$n^2\cdot 2^n \sim 4\times 10^8$，时间限制在5s，正好能过。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 20, M = 1 << 20;
int f[M][N];
int w[N][N];
int main(){
cin >> n;
for(int i = 0; i <= n - 1; i++)
for(int j = 0; j <= n - 1; j++)
cin >> w[i][j];
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 1; i <= (1 << n) - 1; i++){
for(int j = 0; j <= n - 1; j++){
if(i >> j & 1){
for(int k = 0; k <= n - 1; k++){
if(i - (1 << j) >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}