题解【AcWing91】最短Hamilton路径

标签：content   __line__   com   open   passing   using   get   deb   har   

题面

看到数据范围这么小，第一眼想到爆搜。

然而这样做的复杂度是 \(\mathcal{O}(n! \times n)\) 的，明显会 TLE。

于是考虑状压 DP。

我们设 \(dp_{i,j}\) 表示当前走过的集合为 \(i\)，且停留在 \(j\) 号点的最短路径长度。

转移的话可以枚举一个点 \(k\)，意为从 \(k\) 号点走到点 \(j\)，走过的集合变成了 \(i\)。然后就有了转移方程：\(dp_{i,j}=\min\{dp_{i-2^j,k}+a_{k,j}\}\)，其中 \(a_{k,j}\) 表示点 \(k\) 到点 \(j\) 的距离。

注意点的标号从 \(0\) 开始。

这里介绍一个判断 \(j\) 号点是否出现在集合 \(i\) 中的技巧：直接判断 i >> j & 1 是否为 \(\text{true}\) 即可。

#include 
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi

using namespace std;

typedef long long LL;
typedef pair  PII;
typedef pair  PIII;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c  '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c  '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c > j & 1) //判断集合 i 中是否含有 j
            {
                for (int k = 0; k > k & 1) //判断没有访问 j 之前有没有访问过 k
                    {
                        dp[i][j] = min(dp[i][j], dp[i - (1 

题解【AcWing91】最短Hamilton路径

标签：content   __line__   com   open   passing   using   get   deb   har   

原文地址：https://www.cnblogs.com/xsl19/p/12305775.html