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;
}
|