一般动规都是思考我要到D点 我是怎样从别的地方过来的的
但是本题我利用了我要到达k点 应该是用j点过来的 也就是 我从现在的点能到那些点去。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int mp[25][25];
int f[1 <<20][25];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>mp[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)
for(int k=0;k<n;k++)
if(((i>>k)&1)==0)
//顺推过程
f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+mp[j][k]);
//逆推过程
//if(i>>k&1)
// f[i][j]=min(f[i][j],f[i^1<<j][k]+mp[k][j]);
}
cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}