[算法竞赛进阶指南]Hamilton路径(状压dp)
程序员文章站
2024-03-23 21:45:10
...
F : [算法竞赛进阶指南]Hamilton路径
状压dp
dp[i][j]表示在i点处,状态为j下,起点到该点的最短路径
状态0表示不经过,1表示经过
比如dp[3][13],状态13在二进制下是1101,也就是从0到3经过点2,没有过1
在dp过程中,到达该点是从哪个点过来路径最短的,i^1<<j把第j个点的状态取反,即到达第j个点是从状态0101来的
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int n;
int weight[25][25]; //保存权值
int dp[25][1<<20]; //dp[i][j]表示在i点处,状态为j下,起点到该点最短路径为dp[i][j]
int findMin(int n)
{
memset(dp,INF,sizeof(dp));
dp[0][1]=0; //起点赋初值,只经过了0路径为0
for(int i=1;i<1<<n;i++) //枚举所有状态,在所有状态下,起点到各点的最短路径
{
for(int j=0;j<n;j++)
{
if(i&(1<<j)) //取出状态i中第j个点的状态,如果是1表示经过
{
for(int k=0;k<n;k++) //判断在经过j点前还经过哪些点
{
// i^1<<j把i在二进制下的第j位取反,因为此前还没有到达过j点
if((i^1<<j)>>k&1) //在经过j点前,是否经过第k个点,比如1101,在到达第2个点时,是否经过了第0,1,3点,这个状态表示不经过1点
{
dp[j][i]=min(dp[j][i],dp[k][i^1<<j]+weight[j][k]);
}
}
}
}
}
return dp[n-1][(1<<n)-1];
}
int main()
{
//freopen("test.txt","r",stdin);
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>weight[i][j];
}
}
cout<<findMin(n)<<endl;
return 0;
}