这篇题解在你谷上过不去，只有95，NKOJ过了

这道题 $k\le 20$，明示状压DP。

设计状态：第一维显然就是表示当前经过了哪几个点（包括1），我们发现这样还不能确定一个完整的状态，于是第二维表示当前在哪个点。

状态：设 $dp[i][j]$ 表示停留了 $i$ 中的所有点，当前在 $j-1$ 个点（减一是为了给状压DP带来方便），需要走的最短距离。

方程：$dp[i][j] = dp[i][j]+dp[t][k]+dis[k+1][j+1]$ （$j$ 是 $i$ 的一个二进制位，$t$ 是 $i$ 去掉第 $j$ 个点得到的集合，$k$ 是 $t$ 的一个二进制位，$dis[u][v]$ 表示 $u$，$v$ 两点间的距离。

这个方程基本不用解释吧……

然后用 $mp[u][v]$ 表示必须先停留在点 $u$ 再停留在点 $v$，找到入度为 $0$的点大法师就行了。将停留点 $i$ 前必须停留的点记为 $prep[i]$。

$OK[S]=true$表示状态 $S$ 不合法，能起到一些玄学的优化作用（也许？

关于Dijkstra，它死了

关于SPFA，它诈尸了

~~然而是因为NKOJ开了O2速度不到你谷一半造成的，理论上Dijkstra能过。~~

时间复杂度：$O(2^k\cdot k^2+SPFA玄学\cdot mk)$

~~这复杂度劝你重新做个人~~

注：这样在你谷会MLE爆零，用unordered_map代替就 $95pts$ 了。

$Code:$

#include <cstdio>
#include <queue>
#include <cstring>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)
inline int min(int x, int y) {return x < y ? x : y;}

char buf[131072], *p1 = buf, *p2 = buf;
inline int read() {
char ch;
int x(0);
while ((ch = gc) < 48);
while (ch >= 48) x = x * 10 + ch - 48, ch = gc;
return x;
}

struct Edge {
int to, v, nxt;
} e[200005];

int dis[22][20001], dp[1 << 21][22], head[20001], prep[22], tot, K, n, m, t;
bool vis[22][20001], flag[1 << 21][22], mp[22][22], In[22];
std::queue<int> q;

inline void AddEdge(int u, int v, int w)  {
e[++ tot].to = v, e[tot].nxt = head[u], e[tot].v = w, head[u] = tot;
}

inline int SPFA(int st) {
q.push(st);
int *Dis = dis[st];
bool *Vis = vis[st];
memset(dis[st], 0x3f, sizeof(dis[st]));
Dis[st] = 0;
while (q.size()) {
int u(q.front());
q.pop();
Vis[u] = 0;
for (int i(head[u]); i; i = e[i].nxt) {
int v(e[i].to);
if (Dis[u] + e[i].v < Dis[v]) {
Dis[v] = Dis[u] + e[i].v;
if (!Vis[v]) q.push(v), Vis[v] = 1;
}
}
}
}

inline void dfs(int u, int before) {
prep[u] |= before;
for (int i(2); i <= K; ++ i)
if (mp[u][i]) dfs(i, before | 1 << u - 1);
}

inline int DP() {
memset(dp, 0x3f, sizeof(dp));
dp[1][1] = 0;
for (int i(2); i < 1 << K; ++ i)
for (int j(0); j < K; ++ j) if (i & 1 << j) {
int t(i ^ 1 << j);
if ((prep[j + 1] | t) > t) continue;
for (int k(0); k < K; ++ k)
if (t & 1 << k) dp[i][j] = min(dp[i][j], dp[t][k] + dis[k + 1][j + 1]);
}
int ans(0x3fffffff);
for (int j(0); j < K; ++ j) ans = min(ans, dp[(1 << K) - 1][j] + dis[j + 1][n]);
return ans;
}

int main() {
int n(read()), m(read());
K = read() + 1;
while (m --) {
int u(read()), v(read()), w(read());
AddEdge(u, v, w), AddEdge(v, u, w);
}
int t(read());
while (t --) {
int u(read()), v(read());
mp[u][v] = 1, In[v] = 1;
}
for (int i(2); i <= K; ++ i) SPFA(i);
for (int i(2); i <= K; ++ i)
if (!In[i]) dfs(i, 0);
printf("%d", DP());
return 0;
}

zqs`s blog

NKOJ 3761 送外卖

这篇题解在你谷上过不去，只有95，NKOJ过了

关于Dijkstra，它死了

关于SPFA，它诈尸了

$Code:$