最短Hamilton路径

题目link：https://www.acwing.com/problem/content/93/

注意，本题解中，存点为 $0$ ~ $n$ $-$ $1$ ，二进制最低位为第 $0$ 位。

二进制压缩状态，第 $a$ 位为 $1$ 表示第 $a$ 个点走过了，否则没有走过。

考虑朴素的 SPFA 做法，需要记录走到的点。此题还需要记录当前状态，即哪些走/没走过（二进制来表示）。

设 $dis[x][u]$ 表示当前状态为 $x$ ，从 $0$ 到 $u$ 的最短路径（含义见上）。设 $u$ 通过第 $i$ 条边到达了点 $k$ 。

对于每个 $dis[x][u]$ 在 SPFA 中更新 $k$ 的操作，除了需要判断是否满足最短路之外，还需要判断当前状态是否走过 $k$ ，用二进制运算可以轻松算出，即判断 $x$ & $(1$ $<<$ $k)$ $==$ $0$ 。然后在更新中， $k$ 的状态容易得出为 $x$ $|$ $(1$ $<<$ $k)$ 。

最后结果为当所有点都经过，并且结束点为 $n$ $-$ $1$ ，即 $dis[(1$ $<<$ $n)$ $-$ $1][n$ $-$ $1]$ 。

代码就很简单了，注意数组大小，不要 MLE 。

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, head[21], vis[(1 << 20) + 10][21], dis[(1 << 20) + 10][21], num;
 5 struct node {int next, to, val;}stu[810];
 6 void add(int x, int y, int z) {stu[++num].next = head[x]; stu[num].to = y; stu[num].val = z; head[x] = num;}
 7 void spfa()
 8 {
 9     queue < pair < int, int > > pru;
10     memset(dis, INF, sizeof(dis));
11     pru.push(make_pair(1, 0));
12     dis[1][0] = 0, vis[1][0] = 1;
13     while(!pru.empty())
14     {
15         int x = pru.front().first, u = pru.front().second;
16         pru.pop(); vis[x][u] = 0;
17         for(int i = head[u]; i; i = stu[i].next)
18         {
19             int k = stu[i].to;
20             if((x & (1 << k)) == 0 && dis[x | (1 << k)][k] > dis[x][u] + stu[i].val)//== 和 & 的优先级！！！
21             {
22                 dis[x | (1 << k)][k] = dis[x][u] + stu[i].val;
23                 if(!vis[x | (1 << k)][k]) vis[x | (1 << k)][k] = 1, pru.push(make_pair(x | (1 << k), k));
24             }
25         }
26     }
27     return;
28 }
29 int main()
30 {
31     scanf("%d", &n);
32     for(int i = 0; i < n; ++i)
33         for(int j = 0, x; j < n; ++j)
34             scanf("%d", &x), add(i, j, x), add(j, i, x);
35     spfa();
36     printf("%d", dis[(1 << n) - 1][n - 1]);
37     return 0;
38 }