AcWing 91. 最短Hamilton路径
标签：简单 多少 状压dp mil max amp for mem col
状压DP，对于这种范围给到20的，1
#include #define LL long long
using namespace std;
int n;
int maps[30][30];
const int maxx = (120)+2;
int d[maxx][20];
const int INF = 0x3f3f3f3f;
int main(){
while(~scanf("%d",&n)){
for (int i=0;i){
for (int j=0;j){
scanf("%d",&maps[i][j]);
}
}
memset(d,0x3f,sizeof(d));
d[1][0]=0;
for(int i=1;i1){
for (int j=0;j){
if((i>>j)&1){
//代表走过的点中有第j号点，i的第j位置的二进制位不为0
for (int k=0;k){
if((i^(1>k & 1){
d[i][j]=min(d[i][j],d[i^(1maps[j][k]);
}
}
}
}
}
printf("%d\n",d[(11][n-1]);
}
return 0;
}
AcWing 91. 最短Hamilton路径
标签：简单 多少 状压dp mil max amp for mem col
原文地址：https://www.cnblogs.com/bluefly-hrbust/p/12056345.html
评论