AcWing 731. 毕业旅行问题(简单状压dp)
原题链接
中等
作者:
逸误
,
2024-03-29 19:59:07
,
所有人可见
,
阅读 7
//dp,f[1<<20][20]需要80mb内存,不会超。第一维:状态,第二维:最后一步
//第一维从小到大就是合适的顺序,对于每个后面的二进制数,某个1改为0的二进制数肯定已经算过了
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1<<20, M = 21;
int n;
int f[N][M];
int g[M][M];
int main()
{
scanf("%d",&n);
//将整体号码-1,方便状态压缩!
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&g[i][j]);
memset(f,0x3f,sizeof f);
f[1][0]=0;//只去过北京,北京是0号结点(1<<0)
for(int i=1;i<1<<n;i+=2)//遍历状态,不可能有没去过北京的状态
for(int j=0;j<n;j++)//遍历这次终点
if(i>>j&1)//状态里走过这个点
for(int k=0;k<n;k++)
if((i-(1<<j))>>k&1)
{
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+g[k][j]);
}
int res=0x3f3f3f3f;
for(int i=1;i<n;i++)
res=min(res,f[(1<<n)-1][i]+g[i][0]);
printf("%d\n",res);
return 0;
}