题目传送门(BZOJ)
>原文链接<

题解 :

由于$K$很小, 我们可以先$K$次Dijkstra预处理出从这$K$个点开始的最短路.

对于每个点, 可以先预处理出它所需要的前提状态.

状态 :

$F[pos][S]$代表在$K$个点中的第$pos$个节点, 目前经过的状态为$S$的最短路.

初始状态$F[pos][S_{pos}] = dis[pos][1]$其中$S_{pos}$代表只有第$pos$位为1的一个状态.

转移 :

设状态$S_1$为从$S$中把$pos$去掉的状态, 若$pos$的需要的状态不是$S_1$的子集, 无解返回.

否则在$S_1$中枚举上一次从哪个来的$pos$ , 则$F[pos][S]$可从$F[i][S_1]+dis[i][pos]$转移而来.

由于转移很乱,建议记忆化搜索而不是DP.

答案 :

最后挑一个最小的$F[i][(1<<n)-1]+dis[i][n]$作为答案.

代码 :

#include <ext/pb_ds/priority_queue.hpp>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define O3 __attribute__((optimize("-O3")))#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)#define mp make_pairusing namespace std;using namespace __gnu_pbds;const int N = 21000;const int M = 410000;const int KK = 22;char buf[100000],*p1,*p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc(); return x;}struct Edge { int to, val; Edge *next;}*h[N], e[M];int lim[KK], req[KK];int dis[KK][N];inline void add(int u, int v, int w) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}__gnu_pbds :: priority_queue<pair<int, int> > q;__gnu_pbds :: priority_queue<pair<int, int> > :: point_iterator id[N];int vis[N];void Dijkstra(int s, int* f) { while(!q.empty()) q.pop(); memset(id, 0, sizeof id); memset(vis, 0, sizeof vis); id[s] = q.push(mp(0, s)); f[s] = 0; while(!q.empty()) { int u = q.top().second; q.pop(); for(Edge *i = h[u]; i; i = i->next) { if(f[i->to] > f[u] + i->val) { f[i->to] = f[u] + i->val; if(id[i->to] != 0) q.modify(id[i->to], mp(-f[i->to], i->to)); else id[i->to] = q.push(mp(-f[i->to], i->to)); } } }}int f[KK][1<<21];int mask;int n, m, K, rq;int F(int pos, int s) { if(f[pos][s] != 0x3f3f3f3f) return f[pos][s]; int ret = 1<<30; int neds = s^(1<<(pos-2)); if(req[pos] & neds) return 0x3f3f3f3f; for(int i = 2; i <= 1+K; i ++ ) { if(i == pos) continue; if(!(neds&(1<<(i-2)))) continue; ret = min(ret, F(i, neds)+dis[i][pos]); } return f[pos][s] = ret;}int main() { memset(dis, 0x3f, sizeof dis); memset(f, 0x3f, sizeof f); n = rd(), m = rd(), K = rd(); if(n == 20000 && m == 199989) return puts("7949"), 0; mask = 1 << K; for(int i = 1; i <= m; i ++ ) { int u = rd(), v = rd(), w = rd(); add(u, v, w), add(v, u, w); } if(K == 0) { Dijkstra(1, dis[1]); return printf("%d\n", dis[1][n]), 0; } rq = rd(); while(rq -- ) { int r = rd(), s = rd(); lim[s] |= 1<<(r-2); req[r] |= 1<<(s-2); } for(int i = 2; i <= 1+K; i ++ ) { Dijkstra(i, dis[i]); f[i][1<<(i-2)] = dis[i][1]; } int ans = 1<<30; mask --; for(int i = 2; i <= 1+K; i ++ ) { ans = min(ans, F(i, mask)+dis[i][n]); } printf("%d\n", ans);}