题目: 最短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]≤10^7
输入样例：
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思路:
- 为什么要用状态压缩dp？
因为暴力来求的话要从第二个点（起点是0）开始遍历所有点，第二个点有n-2（除去起点和终点）种可能，第三个点有n-3种可能，最后还要根据路径求长度，那么时间复杂度将是(n-1)!，而n最大是20，所以会超时。而状态压缩dp用二进制表示路径，最大不会超过2^20次方，时间复杂度远远小于 (19)！ - 为什么可以用状态压缩dp？
状态压缩dp归根结底还是dp，我们正常去思考这个问题时可能会想到因为我们要走遍所有点，那么因为根据的变化将会有(18)! 种可能。但是状态压缩dp将这(18)!种可能视为一种可能，而这一种可能是由2^20个子状态（或者我们应该称之为集合）逐步优化得到的。这就是压缩的本质！它将问题从如何在所有排列中找到最优解转化为了如何从有限个子状态中直接优化到最优解，所以它的速度可以比暴力做法快很多很多。
状态压缩的思考层次简直高了一个维度。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=21,M=1<<N;
int w[N][N];
//f[i][j]表示从0走到j这个点，路径是i的所有方案 比如：(1100100)B表示0, 1, 3, 4号点没有走
//我们只关心起点和终点是否是0和j，怎么走的不关心，只要0到n-1个点按顺序摆成二进制大小是i就可以
int f[M][N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
cin>>w[i][j];
}
memset(f,0x3f,sizeof f);
//1代表从0号点走到0号点，只有0这个点是1
f[1][0]=0;
//第一重循环遍历从0出发到每个点的所有路径：1 ~ (1<<n)-1
for(int i=1;i<1<<n;++i)
{
//第二重循环是终点
for(int j=0;j<n;++j)
{
//用i的二进制表示路径，1<<j的含义是在i的二进制上表示出这个点，代表这个点走过了
//两者与操作表示判断i是否走过j，因为我们f[i] [j]的含义是从0走到j并且路径大小是i
if(i&(1<<j))
{
//k代表从0走到j的路径上的倒数第二个点（倒数第一个是j）
//我们要将f[i] [j]从f[i-(1<<j)] [k]+w[k][j]转移过来
for(int k=0;k<n;++k)
{
//i-(1<<j)就是在i这条路径上删除j这个点，要时刻注意我们是在用二进制表示路径
//1<<k同上，表示k这个点在二进制路径中的位置，两者与操作表示从0到j的路径上删除j后仍然包含k这个点
//为什么要删除j这个点？因为我们要从倒数第二步转移到f[i] [j]，此时还没有走到j这个点
if((i-(1<<j))&(1<<k))
{
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
}
}
}
}
}
//(1<<n)-1表示所有点都为1，也即走过所有点
cout<<f[(1<<n)-1][n-1];
return 0;
}
