核心思想: 数位dp
用二进制数 存当前所有点 遍历过为1
遍历i图中j点 若j点走过 则求j点路径长度
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20, M = 1<< N ;
int f[M][N];
int w[N][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); //初始化无穷大 便于取min
f[1][0] = 0; //只有起点走过 且当前点为起点 距离为0
for(int i=1;i< 1 << n;i++) //遍历每一张图
for(int j=0;j<n;j++) //遍历i图中每个点
if(i >> j & 1) // 若j点走过
for(int k= 0;k<n;k++) //遍历j点前一个点k
if(i >> k & 1) //k也走过
//更新f[i][j] = f[去掉i][k] +w
//特别地 当j == k时 f[state][k] 不合法 因为图中必须包含k点
//所有min只会取f[i][j]
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的数值
}