AcWing 91. 最短Hamilton路径(状态压缩dp)
原题链接
中等
作者:
逸误
,
2023-08-05 06:12:04
,
所有人可见
,
阅读 86
/*我们只关心
1.哪些点被遍历过
2.最后停在哪个点上
因此,f[state][j]二维可存储这个dp问题
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20,M = 1<<20;
int n;
int f[M][N];//前面是状态(遍历过的点),后面是终点位置,属性:最短距离
//根据位运算的做法,状态要看成二进制的n个0/1
int w[N][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);
f[1][0]=0;//这样初始化是因为题目要求起点是0号点,第一维的[1]其实是000...01
for(int i=0;i<1<<n;i++)//遍历所有的状态
for(int j=0;j<n;j++)
if(i>>j&1)//二进制数i的第j位是1
//上面这两行,将这个状态的每一个点作为终点拿出来算了一次
for(int k=0;k<n;k++)//k表示走到j这个终点之前,以k为终点的最短距离
//因为求最短距离就是求min(上一步状态)+上一步距离
if(i>>k&1&&k!=j)//以所有其他点为上一步的终点来遍历
{
int last_state=i-(1<<j);//这里,[i-(1<<j)]就是去掉i中j这个二进制位置的1后的状态(上一步的状态)
f[i][j]=min(f[i][j],f[last_state][k]+w[k][j]);//求最短距离
}
cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离
//位运算的优先级低于'+'-'所以有必要的情况下要打括号
return 0;
}