最短Hamilton路径
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。
Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
1≤n≤20
0≤a[i,j]≤107
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18
思路分析：
这道题很容易想到的朴素算法，枚举n个点的全排列。
时间复杂度为O((n * n!))
使用下面的状态压缩dp可以优化到O((n^2 * 2 ^ n))
比如在 0, 1, 2, 3 这几个点中，我们需要从0 -> 3
0 -> 2 -> 1 -> 3 所需10
0 -> 1 -> 2 -> 3 所需20
我们肯定只选第一条路
很容易理解，若还有其他的点，第二条路总是会比第一条花费多，
所以第二条边没有维护的必要，可以给它删除，保留第一条这条更优的。
注意，删除的前提是他们二者访问的点的个数是一样的，现在在的点的位置是一样的。
但朴素的爆搜还是会搜下去，直到搜完全部点。
这就是主要优化的地方。
(可以去看一下 Acwing y总的视频讲解，本人虽然知道 状压dp 的时间复杂度比 爆搜 要低
但一直搞不清楚它这个 状压dp 优化在哪，看了y总的讲解恍然大悟)
最大有20个点，为了表示每个点的状态和当前点的位置
可以开一个f[1 << 20][20]来记录 在 i 状态 j 位置的最小代价
i 状态 j 位置 的代价 需要从 i 状态 下访问过 且 不为j 的k点来到达
只需要f[i][j] = min(f[i][j], f[i - (1<<j)][k])
下方代码有本人认为根据本题要求可以做出的一些小优化?注释标注。
代码展示：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 25;
int n, g[N][N], f[1 << 20][20]; // i 状态 j位置
inline void work (int n) {
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for(int i = 1; i < 1 << n; i += 2) // 修改 i ++ -> i += 2。遍历状态
for(int j = 1; j < n; j ++) if((i >> j) & 1) // j = 0 -> j = 1。 遍历结束点
for(int k = 0; k < n; k ++) if((i ^ 1<<j)>>k & 1) //遍历到结束点的点
f[i][j] = min(f[i][j], f[i ^ 1<<j][k] + g[k][j]);
printf("%d", f[(1 << n) -1][n - 1]);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
scanf("%d", &g[i][j]);
work(n);
return 0;
}