基本算法题. 最短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:four_leaf_clover:题解 --- 状态压缩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
此时我们可以果断做决定:走sixth，而此时0~5的最短距离为(17+3走到5的距离)(假设3–>5=5)
在以上两大类情况之后我们可以得出当走到5时:
1.以4为终点的情况的最短距离是:15+8=23;
2.以3为终点的情况的最短距离是:17+5=22;
经过深思熟虑之后,商人决定走以3为终点的最短距离,此时更新最短距离为:22。
当然以此类推还会有以1为终点和以2为终点的情况，此时我们可以进行以上操作不断更新到5这个点的最短距离，最终可以得到走到5这个点儿的最短距离，然后再返回最初的假设，再依次假设1,2,3,4是终点，最后再不断更新，最终可以得出我们想要的答案。
状态转移方程：fi=min(fi,fi-(1<<j)+wk)
:memo:代码展示
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20,M=1<<N;
int f[M][N],w[N][N];// w为无权图
int main()
{
int n;
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));// 由于要求最小值，故初始化为无穷大
f[1][0]=0;// 零是起点
for(int i=0;i<1<<n;i++)// i表示所有的情况
for(int j=0;j<n;j++)// j表示走到哪一个点
if(i>>j&1)
for(int k=0;k<n;k++)// k表示走到j这个点之前,以k为终点的最短距离
if(i>>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;// 表示所有点都走过,且终点是n-1的最短距离
// 注意位运算的优先级低于'+'-'
return 0;
}【知识点：状态压缩DP】
状态压缩动态规划，顾名思义，状态压缩动态规划这个算法包括两个特点，第一是 “状态压缩” ，第二是 “动态规划” 。
从 状态压缩 的特点来看，这个算法 适用的题目 符合以下的条件：
1.解法需要保存一定的状态数据（表示一种状态的一个数据值），每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态，比如说棋盘上的格子，放棋子或者不放，或者是硬币的正反两面。这样用0或者1来表示状态数据的每个单元，而整个状态数据就是一个一串0和1组成的二进制数。
2.解法需要将状态数据实现为一个基本数据类型，比如int，long等等，即所谓的状态压缩。状态压缩的目的一方面是缩小了数据存储的空间，另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大，比如用int来表示一个状态的时候，状态的单元个数不能超过32（32位的机器）。
说到 动态规划 ：
如果说状态压缩是数据结构的话，那么动态规划应该是算法了。题目通过动态规划来解通常有两个动机，第一是利用递归的重叠子问题，进行记忆话求解，即递归法的优化。第二是把问题看作多阶段决策的过程来求解问题。在状态压缩动态规划中我们讨论的是第二种动机。
