最短路+状压dp
肯定是状压dp
那么我们把k个点的单源最短路预处理出来，然后dp[i][j]表示状态为i，当前在j需要走的最短距离，给定的限制用状态压一下就行了
注意特判k=0的情况
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N = 20010, D = 20; struct edge { int nxt, to, w; } e[N * 20]; int n, m, k, cnt = 1, ans = 0x3f3f3f3f, L; int head[N], dp[1 << D][D], d[D][N], id[D], can[D]; inline void read(int &x) { x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); } x *= f; } void link(int u, int v, int w) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; e[cnt].w = w; } void dijkstra(int s, int *d) { priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; d[s] = 0; q.push(make_pair(0, s)); while(!q.empty()) { pair<int, int> o = q.top(); q.pop(); int u = o.second; if(d[u] < o.first) continue; for(int i = head[u]; i; i = e[i].nxt) if(d[e[i].to] > d[u] + e[i].w) { d[e[i].to] = d[u] + e[i].w; q.push(make_pair(d[e[i].to], e[i].to)); } } } int main() { // freopen("travel.in", "r", stdin); // freopen("travel.out", "w", stdout); read(n); read(m); read(k); for(int i = 1; i <= m; ++i) { int u, v, w; read(u); read(v); read(w); link(u, v, w); link(v, u, w); } memset(d, 0x3f3f, sizeof(d)); read(L); for(int i = 0; i < k; ++i) id[i] = i + 2, dijkstra(id[i], d[i]); for(int i = 1; i <= L; ++i) { int u, v; read(u); read(v); can[v - 2] |= (1 << (u - 2)); } if(k == 0) { dijkstra(1, d[0]); printf("%d ", d[0][n]); return 0; } memset(dp, 0x3f3f, sizeof(dp)); for(int i = 0; i < k; ++i) if(!can[i]) dp[1 << i][i] = d[i][1]; for(int i = 0; i < (1 << k); ++i) for(int j = 0; j < k; ++j) if(i & (1 << j)) for(int x = 0; x < k; ++x) if(!(i & (1 << x)) && ((i & can[x]) == can[x])) dp[i ^ (1 << x)][x] = min(dp[i ^ (1 << x)][x], dp[i][j] + d[j][id[x]]); for(int i = 0; i < k; ++i) ans = min(ans, dp[(1 << k) - 1][i] + d[i][n]); printf("%d ", ans); // fclose(stdin); // fclose(stdout); return 0; }