-
Notifications
You must be signed in to change notification settings - Fork 0
/
2359.cpp
111 lines (87 loc) · 1.36 KB
/
2359.cpp
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//2359
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
#define INF 1001001001
#define cost first
#define id second
int dijkstra(vector<ii> G[], bool has_h[], int src, int size)
{
priority_queue<ii, vector<ii>, greater<ii>> pq;
int cost[size + 1]; fill(cost, cost + size + 1, INF);
cost[src] = 0;
pq.push(ii(0, src));
while(!pq.empty())
{
ii u = pq.top(); pq.pop();
if(has_h[u.id]) return cost[u.id];
if(cost[u.id] != u.cost) continue;
for(int j = 0; j < (int)G[u.id].size(); j++)
{
ii v = G[u.id][j];
if(cost[u.id] + v.cost < cost[v.id])
{
cost[v.id] = cost[u.id] + v.cost;
pq.push(ii(cost[v.id], v.id));
}
}
}
return INF;
}
int main()
{
int n, m, q;
while(scanf("%d%d%d", &n, &m, &q) != EOF)
{
vector<ii> G[n];
bool has_h[n];
fill(has_h, has_h + n, false);
for(int a = 0; a < m; a++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u--, v--;
G[u].push_back(ii(w, v));
G[v].push_back(ii(w, u));
}
while(q--)
{
int h;
scanf("%d", &h);
h--;
has_h[h] = true;
}
int t = 0;
for(int u = 0; u < n; u++)
{
if(!has_h[u])
{
int tl = dijkstra(G, has_h, u, n);
if(tl > t) t = tl;
}
}
printf("%d\n", t);
}
}
/*
4 4 1
1 2 3
2 3 1
4 2 2
4 3 4
4
5 8 5
1 2 1
2 3 2
5 4 3
1 4 4
1 5 5
2 5 6
4 3 7
2 4 8
1
2
3
4
5
*/