AcWing 91. 最短Hamilton路径 压缩dp

AcWing 91. 最短Hamilton路径

给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数n。

接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(记为a[i,j])。

对于任意的x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式
输出一个整数,表示最短Hamilton路径的长度。

数据范围

1≤n≤20
0≤a[i,j]107

输入样例:

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例:

18

思路

刚开始我想到用并查集来去做,但是我想到集合不一定是一条线,所以我想了用贪心,还是没做出来。看了y总的方法,把路径压缩成一个二进制,我觉得真的想不到啊。

d p [ i ] [ j ] dp[i][j] dp[i][j]表示经过路径i到达j点的最短距离。
i的二进制拆开,0表示不经过,1表示经过。
然后开始状态计算
d p [ i ] [ j ] = 【 d p [ i − 1 < < j ] [ k ] + w [ k ] [ j ] … … 】 dp[i][j]={【dp[i-1<dp[i][j]=dp[i1<<j][k]+w[k][j]
其中k表示经过j前一个点,i-1< y总视频

代码如下

#include
#include
#include

using namespace std;

const int N=21,M=1<<21;

int dp[M][N];
int dist[N][N];

int main()
{
     
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    cin>>dist[i][j];
    
    memset(dp,0x3f,sizeof dp);
    
    dp[1][0]=0;
    
    for(int i=0;i<1<<n;i++)
    for(int j=0; j<n; j++)
    {
     
        if(i>>j&1)
        {
     
            for(int k=0;k<n;k++)
            {
     
                if(i>>k&1)
                dp[i][j]=min(dp[i-(1<<j)][k]+dist[k][j],dp[i][j]);
            }
        }
    }
    printf("%d",dp[(1<<n)-1][n-1]);
}

你可能感兴趣的