id="关键词状压使用场景思路应用">关键词：状压使用场景、思路、应用

状压dp是字面意思将状态压缩，一般是压缩至二进制，所以n需要很小，普遍都是

id="例题1简化题目从00出发走过所有节点的最短路长度多少">例题1：简化题目从(0,0)出发，走过所有节点的最短路长度多少

设f[mark][i]定义为状态为mark且最后到达第i个奶酪位置,mark状态定义为当第j位为1的时候表示经过第j个奶酪的位置

sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2));
int
s=0;s<(1<<n);s++){for(int
i=1;i<=n;i++){f[s][i]=inf;}}for(int
i=1;i<=n;i++){cin>>a[i].x>>a[i].y;f[1<<(i-1)][i]=add(0,i);}for(int
s=0;s<(1<<n);s++){for(int
i=1;i<=n;i++){if(!(s&(1<<(i-1))))continue;for(int
j=1;j<=n;j++){if(s&(1<<(j-1)))continue;f[s|(1<<(j-1))][j]=min(f[s|(1<<(j-1))][j],f[s][i]+add(i,j));}}}double
ans=inf;for(int
i=1;i<=n;i++){//cout<<f[(1<<n)-1][i]<<"
";ans=min(ans,f[(1<<n)-1][i]);}printf("%.02lf\n",ans);return