scx 想从成都去上海旅游。在旅途中她希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他有趣的事情。
经过这些城市的顺序不是完全随意的，比如说 scx 不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。
幸运的是，scx 的旅程不是既定的，她可以在某些旅行方案之间进行选择。由于 scx 非常讨厌乘车的颠簸，她希望在满足她的要求的情况下，旅行的距离尽量短，这样她就有足够的精力来欣赏风景或者是 ██████ 了 ^_^。
整个城市的交通网络包含 $n$ 个城市以及城市与城市之间的双向道路 $m$ 条。城市自 $1$ 至 $n$ 依次编号，道路亦然。没有从某个城市直接到它自己的道路，两个城市之间最多只有一条道路直接相连，但可以有多条连接两个城市的路径。
任意两条道路如果相遇，则相遇点也必然是这 $n$ 个城市之一，在中途，由于修建了立交桥和下穿隧道，道路是不会相交的。每条道路都有一个固定长度。
在中途，scx 想要经过 $k$ ($k \leq n-2$) 个城市。成都编号为 $1$，上海编号为 $n$，而 scx 想要经过的 $n$ 个城市编号依次为 $2, 3, \cdots, k+1$。举例来说，假设交通网络如下图：
scx 想要经过城市 $2, 3, 4, 5$，并且在 $2$ 停留的时候在 $3$ 之前，而在 $4, 5$ 停留的时候在 $3$ 之后。那么最短的旅行方案是 $1 \to 2 \to 4 \to 3 \to 4 \to 5 \to 8$，总长度为 $19$。
注意 scx 为了从城市 $2$ 到城市 $3$ 可以路过城市 $4$，但不在城市 $4$ 停留，这样就不违反 scx 的要求了。并且由于 scx 想要走最短的路径，因此这个方案正是 scx 需要的。
第一行包含三个整数 $n, m, k$ ($2 \leq n \leq 20000; 1 \leq m \leq 2 \times 10^5; 0 \leq k \leq \min \{20, n-2\}$)，意义如上文所述。
接下来的 $m$ 行描述路径，每行三个整数，第 $i+1$ 行的 $p_i, q_i, l_i$ ($1 \leq p_i < q_i \leq n; 1 \leq l_i \leq 1000$)，表示pi和qi之间有一条长为li的路。
接下来一行一个整数 $g$ ($0 \leq g \leq \dbinom k 2$)，表示有 $g$ 个要求。
接下来 $g$ 行，每行两个整数 $r_i, s_i$ ($2 \leq r_i, s_i \leq k+1; r_i \neq s_i$)，表示在 $s_i$ 停留之前要先在 $r_i$ 停留 (停留不等于经过)。
输出一行一个整数，表示最短的旅行距离。
其实经过这件事情还算好办，只要确定了相邻两个停留点，直接取它们的最短路即可，管它是怎么走的。
如果 $k = 0$，那么显然只是一个最短路。主要考虑 $k \neq 0$，由于它是按照一定次序经过前 $k$ 个城市。注意到 $k \leq 20$，因此可以想到使用状压 DP。
不过在这之前，我们需要预处理出前 $k+1$ 个点的最短路，注意不能直接 $O(k^3)$ Floyd，需要跑 $k$ 遍 Dijkstra，因为中途点可能不是前 $k+1$ 个点。
记 $f_{i, S}$ 表示当前停留到城市 $i$，经过的城市集合为 $S$ ($S \subseteq \{2, 3, \cdots, k+1\}$)，那么 $f_{1, \varnothing} = 0$，其它 $f_{i, S} = + \infty$。考虑下一个城市为 $j$，那么必须满足 $\mathrm{pre} (j) \subseteq S$，其中 $\mathrm{pre} (j)$ 即为要达到城市 $j$ 所需要的前趋城市集合，即必须在它所需要的所有城市停留过。
那么转移就很简单了，记 $i$ 到 $j$ 的最短路为 $\mathrm{dist} (i, j)$，那么 $$ f_{j, S \cup \{j\}} \downarrow f_{i, S} + \mathrm{dist} (i, j) $$
最后的答案只需简单处理一下，由于终点相当于所有前 $k+1$ 个城市都经过，因此枚举最后停留的城市 $i$，那么总距离即为 $f_{i, U} + \mathrm{dist} (i, n)$，其中 $U$ 是全集 $\{2, 3, \cdots, k+1\}$。总时间复杂度 $O \left( k (m \log n + 2^k k) \right)$。
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#define N 20034
#define M 426835
#define K 24
#define K2 1109771
#define INF 0x3f3f3f3f
using __gnu_pbds::priority_queue;
struct edge{
int u, v, w;
edge(int u0 = 0, int v0 = 0, int w0 = 0): u(u0), v(v0), w(w0) {}
}e[M];
int V, E, n, q;
int u, v, w, i, j, k;
int first[N], next[M];
int dis[K][N], pre[K];
int ans, f[K][K2];
inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline void addedge(int u, int v, int w){
e[++q] = edge(u, v, w); next[q] = first[u]; first[u] = q;
e[++q] = edge(v, u, w); next[q] = first[v]; first[v] = q;
}
namespace shortest_path{
struct _{
int to, dist;
_ (int to0 = 0, int dist0 = 0): to(to0), dist(dist0) {}
bool operator < (const _ &b) const {return dist > b.dist;}
};
priority_queue <_> pq;
void Dijkstra(int si){
int i, *d = dis[si]; _ t;
pq.push(_(si, 0)); d[si] = 0;
for(; !pq.empty(); ){
t = pq.top(); pq.pop();
if(t.dist != d[t.to]) continue;
for(i = first[t.to]; i; i = next[i])
if(t.dist + e[i].w < d[e[i].v]){
d[e[i].v] = t.dist + e[i].w;
pq.push(_(e[i].v, d[e[i].v]));
}
}
}
}
int main(){
scanf("%d%d%d", &V, &E, &n);
for(i = 1; i <= E; ++i) {scanf("%d%d%d", &u, &v, &w); addedge(u, v, w);}
memset(dis, 63, sizeof dis);
for(i = 1; i <= n + 1; ++i) shortest_path::Dijkstra(i);
for(scanf("%d", &q); q; --q) {scanf("%d%d", &u, &v); pre[v] |= 1 << u - 2;}
memset(f, 63, sizeof f);
f[1][0] = 0;
for(j = 0; j < 1 << n; ++j)
for(i = 1; i <= n + 1; ++i)
if(f[i][j] < INF)
for(k = 2; k <= n + 1; ++k)
if(!(~j & pre[k]))
down(f[k][j | 1 << k - 2], f[i][j] + dis[i][k]);
ans = INF;
for(i = 1; i <= n + 1; ++i) down(ans, f[i][(1 << n) - 1] + dis[i][V]);
printf("%d\n", ans);
return 0;
}
坑1：注意状压 DP 的时候的枚举顺序！一定要枚举集合 $S$，再枚举停留的城市 $i$。因为如果先枚举 $i$ 的话，后面的 $i$ 可能还会更新前面的 $i$，而 $S$ 中元素一定是越来越多的 (偏序)。如果先枚举 $S$，则在 $S$ 相同的情况下跳来跳去可能是越跳越劣的，因此不会对答案产生影响。