算法
考虑一个集合f[i][j],表示从0经过点集到达j的最短路径,因为共有n个点,每个点都有经过和不经过的情况,那么可以把所有的状态
用一个n位的二进制数存起来,状态转移时,考虑0-j这条路径上的倒数第二个点k,f[i][j]=f[i-{j}][k]+a[k][j],当状态i中包含j和k这两个点的时候
可以进行状态转移
#include<iostream>
#include<cstring>
using namespace std;
const int N=20,M=1<<20;
int a[N][N];
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>>a[i][j];
memset(f,0x3f,sizeof f);//将所有的路径距离初始化为无穷大,这样方便后续计算最短路
f[1][0]=0;//初始化第一个点0-0
for(int i=0;i<1<<n;i++)
for(int j=0;j<n;j++)
if(i>>j&1)//点集中必须包含j这个点,才可以进行状态转移
for(int k=0;k<n;k++)//遍历倒数第二个点的所有情况
if(i>>k&1)//i中必须要有k这个点,不然k不可能在倒数第二个点中。
f[i][j]=min(f[i-(1<<j)][k]+a[k][j],f[i][j]);//这里不需要判断k和j是不是相等的,因为如果j==k,那么i-(1<<j)中
cout<<f[(1<<n)-1][n-1]; //就没有k,也就是说f[i-(1<<j)][k]不合法,它的值为无穷大,不会更新f[i][j].
return 0;
}