AcWing 731. 毕业旅行问题
原题链接
中等
作者:
TYUTICPC05
,
2021-05-15 11:23:42
,
所有人可见
,
阅读 595
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1<<20][22];
int s[22][22];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&s[i][j]);
//0对应的是起点;终点是n-1;
memset(dp,0x3f,sizeof dp);
dp[0][0]=0; //没开始走,在起点花费是0;
for(int i=0;i<1<<n;i++)
{
for(int j=0;j<n;j++) //枚举二进制的每一位
if(i>>j&1) //如果是1 ,就由i-(1<<j)转移过来,再枚举这个状态,
for(int k=0;k<n;k++) //不判断的话, 如果i-(1<<j)第k+1位是0 这个数就在前面没被更新=0x3f3f3f3f;
dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+s[j][k]);
}
cout<<dp[(1<<n)-1][0]; //走完终点是 0 因为s[0][0]=0,所以ans=dp[(1<<n)-1][0];
// _这个先记下,之后再说_
return 0;
}