给定一张 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

思路：

　　如果使用暴力DFS的话，时间复杂度起码也是 20 ！肯定就超时，只能DP了；

　比如说有 4 个点：

   0 —> 1 —> 2 —> 3 —> 4// 在 2 那里可以理解为 ： 已经走过 两个点了，马上要走第三个点 ；这是只要判断 3 点在之前走没走过；若是没走过，则可以有 dp[i][3] = dp[ i _3 ][ 2 ] + a[2][3]；

   0 —> 1 —> 3 —> 2 —> 4

   ……

　i 作为一个数可以使用状态压缩的方式来表示成一个集合：

   若是已经 走过  0，3，4点，则 i = 10001；这样一来，i 就是一个20位的二进制数，为 1 << 20；

　　状态转移方程　　dp[ i ][ j ] = min(dp[ i_k ][ k ] + a[ k ][ j ], dp[ i ][ j ] );

　　　　　　　　　　　　　　// i 表示为状态压缩下的一个集合，集合里面的数表示了该点走没做过， j 表示走过该集合下所有路径的最后一个点

　　　　　　　　　　dp[ i ][ j ] 为已经储存了数个（跟 i 有关）点并且最后一个点为 j ；

　　　　　　　　　　dp[ i_k ][ k ] 为已经储存了除 k 外的所有 i 的点，并且最后一个点为 k；

　　　　　　　　　　a[ k ][ j ] 为 k 到 j 的路径；// 相加即为 把 j 点储存了进去，是最后一个点 k 更新 为 j；

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n, dp[1 << 20][20], a[21][21];
int main() {
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> a[i][j];
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[1][0] = 0;//从 0 开始，只走了 0 点，最短路径自然为0
	for(int i = 0; i < 1 << n; i++){// i 小于 2^n,是一个20位的二进制数
		for(int j = 0; j < n; j++){
			if(i >> j & 1){//判断 i 的第 j 位 是不是1
				for(int k = 0; k < n; k++){//遍历所有点，挨个试着走
					if(i - (1 << j) >> k & 1){//这里还没走到 j 点，所以要用除了 j 点之前的集合，左移运算符优先级小于加减需带上括号。
						dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + a[k][j]);		
					}
				}
			}
		}
	}
	cout << dp[(1 << n) - 1][n - 1] << endl;

	return 0;
}

需要了解的那些知识：
　　右移运算符　　1<< n == 2 ^ n；

　　左移运算符　　1>> n == (1/2) ^ n；i >> j 为 二进制下的 i 的第 j 位；

　　i & 1 即为 i 转换成二进制数的尾数是不是1；