所需知识：二进制状态压缩，动态规划
假设现在有六个点：
| j/i | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 2 | 4 | 5 | 1 | 3 |
| 1 | 2 | 0 | 6 | 5 | 3 | 1 |
| 2 | 4 | 6 | 0 | 8 | 3 | 2 |
| 3 | 5 | 5 | 8 | 0 | 5 | 4 |
| 4 | 1 | 3 | 3 | 5 | 0 | 3 |
| 5 | 3 | 1 | 2 | 4 | 3 | 0 |
起点为0终点为5，假设现在走到终点前一点，不妨设该点为4，即现在要确定从0到4，最少要走多远，起点为1终点为4，现有六条路可以选择：
first: 0–>1–>2–>3–>4 距离:21
second: 0–>1–>3–>2–>4 距离:18
third: 0–>2–>1–>3–>4 距离:17
fourth: 0–>2–>3–>1–>4 距离:20
fifth: 0–>3–>1–>2–>4 距离:19
sixth: 0–>3–>2–>1–>4 距离:22
因为4到5的距离是确定的唯一值，所以0->4的最短路径即为0->5的最短路径，即为此例中的third。
所以得出结论，只要确定最后一点的前一点的最短路径即为答案所求最短路径，因此dp的思路有了，但怎么表示走过的路径还是一个问题，今天刚学了一种方法：状态压缩，用一个数的二进制表示是否走过这个点（1表示走过，0表示没走过）
状态转移方程式：f[i][j]=min(f[i][j],f[i-(1<<j)][k]+a[k][j])；
C++代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20,M=1<<N;
int a[N][N];
int n;
int f[M][N];
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ ){
for (int j = 0; j < n; j ++ ){
cin>>a[i][j];
}
}
memset(f,0x3f,sizeof f);
f[1][0]=0;
for (int i = 0; i <(1<<n); i ++ ){
for (int j = 0; j < n; j ++ ){
if((i>>j)&1)//判断某一个数的第j为是不是1（有没有经过j这个点）
for (int k = 0; k < n; k ++ ){
if((i>>k)&1)//（有没有经过k这个点）
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+a[k][j]);
}
}
}
cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}