BZOJ1097. [POI2007]旅游景点atr
Q3.5.2.1. 旅游景点
- 设 dis[i][j] 表示 i 到 j 的最短路(需要用 k 次 Dijkstra, 因为 i 到 j 可能经过其他点)
- 设 f[i][s] 表示现在在 i 节点, 已经走过 s 这些节点(s是{2,3,...,k+1}的自己,1<=i<=k+1)
f[1][0]=0, f[j][s∪j]=min=f[i][s]+dis[i][j] 答案为min{f[i][全集]+dis[i][n]}
点击查看代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
const int N = 20005, M = 400005, K = 25, S = (1 << 20) + 5;
int n, m, k, q;
int h[N], e[M], w[M], nxt[M], idx;
int dis[K][N];
bool st[N];
int f[K][S];
int pre[K]; // 前置城市
void add(int a, int b, int c) {
e[++ idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx;
}
void Dijkstra(int start, int *dist) {
typedef pair<int, int> PII;
memset(dist + 1, 0x3f, sizeof(*dist) * n);
memset(st + 1, false, sizeof(*st) * n);
priority_queue<PII, vector<PII>, greater<PII> > heap;
heap.push({dist[start] = 0, start});
while(heap.size()) {
int u = heap.top().second;
heap.pop();
if(st[u]) continue;
st[u] = true;
for(int i = h[u]; i; i = nxt[i]) {
int v = e[i];
if(dist[v] > dist[u] + w[i]) {
dist[v] = dist[u] + w[i];
heap.push({dist[v], v});
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1, a, b, c; i <= m; i ++) scanf("%d%d%d", &a, &b, &c), add(a, b, c), add(b, a, c);
for(int i = 1; i <= k + 1; i ++) Dijkstra(i, dis[i]);
for(int i = scanf("%d", &q), a, b; i <= q; i ++) scanf("%d%d", &a, &b), pre[b] |= 1 << (a - 2);
for(int i = 0; i <= k + 1; i ++) for(int s = 0; s < (1 << k); s ++) f[i][s] = 0x3f3f3f3f;
f[1][0] = 0;
for(int s = 0; s < (1 << k); s ++)
for(int i = 1; i <= k + 1; i ++)
if(f[i][s] < 0x3f3f3f3f)
for(int j = 2; j <= k + 1; j ++)
if((s & pre[j]) == pre[j])
f[j][s | (1 << (j - 2))] = min(f[j][s | (1 << (j - 2))], f[i][s] + dis[i][j]);
int res = 0x3f3f3f3f;
for(int i = 1; i <= k + 1; i ++) res = min(res, f[i][(1 << k) - 1] + dis[i][n]);
printf("%d\n", res);
return 0;
}