0%

[洛谷 P4943] 密室

题目

题目链接

题目大意:罗恩和哈利去两个屋子。有些点只能哈利走。问两个目的地被到达的最短时间。$1 \le n \le 50000, 1 \le m \le 100000$。

思路

可能的方案只有两种:哈利和罗恩分别去两个屋子,哈利去两个屋子。

这里可以先求出从起点到各个点的最短路和从一个终点为起点到各个点的最短路,这样比较方便最后答案的更新。

如果是罗恩的话可以在 Dijkstra 的过程中加一个特判。

最后只需要比大小就行了。代码中 $dis_0$ 表示从起点开始哈利离其他点的距离,$dis_1$ 表示从起点开始罗恩离其他点的距离,$dis_2$ 表示从一个终点开始哈利离其他点的距离。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;
typedef unsigned long long uLL;

struct Node {
int pos;
LL dis;
friend bool operator < (const Node &a, const Node &b) {
return a.dis > b.dis;
}
} ;

struct Edge {
int to;
LL w;
} ;

std::vector<Edge> g[50010];
LL dis[3][50010];
int n, m, k, t1, t2;
bool b[50010], vis[50010];

void dijkstra(int s, bool flag, int x) {
for (int i = 1; i <= n; ++i) dis[x][i] = 0x3f3f3f3f, vis[i] = false;
dis[x][s] = 0;
std::priority_queue<Node> q;
q.push((Node){s, 0});
while (!q.empty()) {
Node now = q.top();
q.pop();
if (vis[now.pos]) continue;
vis[now.pos] = true;
for (auto i : g[now.pos]) {
if (flag && b[i.to]) continue;
if (dis[x][i.to] > dis[x][now.pos] + i.w) {
dis[x][i.to] = dis[x][now.pos] + i.w;
q.push((Node){i.to, dis[x][i.to]});
}
}
}
}

int main() {
read(n), read(m), read(k);
for (int i = 1, tmp; i <= k; ++i) read(tmp), b[tmp] = true;
for (int i = 1, u, v, w; i <= m; ++i) {
read(u), read(v), read(w);
g[u].push_back((Edge){v, w}), g[v].push_back((Edge){u, w});
}
read(t1), read(t2);
dijkstra(1, false, 0), dijkstra(1, true, 1), dijkstra(t1, false, 2);
if (!k) {
printf("%lld\n", std::max(dis[0][t1], dis[0][t2]));
} else {
LL min = std::max(dis[0][t1], dis[1][t2]);
min = std::min(min, std::max(dis[0][t2], dis[1][t1]));
min = std::min(min, dis[0][t1] + dis[2][t2]);
min = std::min(min, dis[0][t2] + dis[2][t2]);
printf("%lld\n", min);
}
return 0;
}