注意,本题解中,存点为$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 。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, head[21], vis[(1 << 20) + 10][21], dis[(1 << 20) + 10][21], num;
struct node {int next, to, val;}stu[810];
void add(int x, int y, int z) {stu[++num].next = head[x]; stu[num].to = y; stu[num].val = z; head[x] = num;}
void spfa()
{
queue < pair < int, int > > pru;
memset(dis, INF, sizeof(dis));
pru.push(make_pair(1, 0));
dis[1][0] = 0, vis[1][0] = 1;
while(!pru.empty())
{
int x = pru.front().first, u = pru.front().second;
pru.pop(); vis[x][u] = 0;
for(int i = head[u]; i; i = stu[i].next)
{
int k = stu[i].to;
if((x & (1 << k)) == 0 && dis[x | (1 << k)][k] > dis[x][u] + stu[i].val)
{
dis[x | (1 << k)][k] = dis[x][u] + stu[i].val;
if(!vis[x | (1 << k)][k]) vis[x | (1 << k)][k] = 1, pru.push(make_pair(x | (1 << k), k));
}
}
}
return;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0, x; j < n; ++j)
scanf("%d", &x), add(i, j, x), add(j, i, x);
spfa();
printf("%d", dis[(1 << n) - 1][n - 1]);
return 0;
}