/**
* Author : Nguyen Tuan Vu
* Created : 12.01.2023
**/
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
using namespace std;
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
void file(){
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
}
const int N = 1e5 + 5;
const int INF = 1e9 + 7;
int n, m, K, head[N], dist[N], MIN[2][4], dist2[N];
vector <pair <int, int>> adj[N];
vector <int> Spe, new_Spe;
void dijkstra(vector <int> Spe) {
FOR(i, 1, n) dist[i] = INF;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
for (auto x : Spe) {
head[x] = x;
heap.push({dist[x] = 0, x});
}
while (heap.size()) {
int du = heap.top().first;
int u = heap.top().second;
heap.pop();
if (du != dist[u]) continue;
for (auto v : adj[u]) if (minimize(dist[v.second], dist[u] + v.first)) {
heap.push({dist[v.second], v.second});
head[v.second] = head[u];
}
}
}
int shortest_path(vector <int> Spe) {
dijkstra(Spe);
int D = INF;
FOR(u, 1, n) for (auto x : adj[u]) {
int v = x.second;
if (head[v] != head[u]) {
minimize(D, dist[v] + dist[u] + x.first);
}
}
return D;
}
void dijkstra2(int x, int MIN[], int dist[]) {
FOR(i, 1, n) dist[i] = INF;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
heap.push({dist[x] = 0, x});
while (heap.size()) {
int du = heap.top().first;
int u = heap.top().second;
heap.pop();
if (du != dist[u]) continue;
for (auto v : adj[u]) if (minimize(dist[v.second], dist[u] + v.first)) {
heap.push({dist[v.second], v.second});
head[v.second] = head[u];
}
}
MIN[0] = MIN[1] = MIN[2] = INF;
for (auto z : Spe) if (z != x) {
if (dist[z] < MIN[0]) {
MIN[3] = MIN[2];
MIN[2] = MIN[1];
MIN[1] = MIN[0];
MIN[0] = dist[z];
}
else if (dist[z] < MIN[1]) {
MIN[3] = MIN[2];
MIN[2] = MIN[1];
MIN[1] = dist[z];
}
else if (dist[z] < MIN[2]) {
MIN[3] = MIN[2];
MIN[2] = dist[z];
}
else minimize(MIN[3], dist[z]);
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
file();
cin >> n >> m >> K;
FOR(i, 1, m) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
FOR(i, 1, K) {
int x; cin >> x;
Spe.push_back(x);
}
dijkstra(Spe);
int A = 0, B = 0, D = INF;
FOR(u, 1, n) for (auto x : adj[u]) {
int v = x.second;
if (head[v] != head[u] && minimize(D, dist[v] + dist[u] + x.first)) {
A = head[u];
B = head[v];
}
}
//cout << A << ' ' << B << '\n';
for (auto x : Spe) if (x != A && x != B) new_Spe.push_back(x);
int res = 2 * INF;
minimize(res, shortest_path(Spe) + shortest_path(new_Spe));
dijkstra2(A, MIN[0], dist);
dijkstra2(B, MIN[1], dist2);
for (auto x : Spe) if (x != A && x != B) {
int cost = dist2[x];
int bonus = 0;
if (MIN[0][0] == dist[x] || MIN[0][0] == dist[A] || MIN[0][0] == dist[B]) {
if (MIN[0][1] == dist[x] || MIN[0][1] == dist[A] || MIN[0][1] == dist[B]) {
if (MIN[0][2] == dist[x] || MIN[0][2] == dist[A] || MIN[0][2] == dist[B]) {
bonus = MIN[0][3];
}
else bonus = MIN[0][2];
}
else bonus = MIN[0][1];
}
else bonus = MIN[0][0];
minimize(res, cost + bonus);
}
cout << res;
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
RelayMarathon.cpp: In function 'void file()':
RelayMarathon.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2684 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2680 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2680 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
3 ms |
2676 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2684 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
2 ms |
2644 KB |
Output is correct |
25 |
Correct |
2 ms |
2680 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2680 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2684 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2680 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2680 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
3 ms |
2676 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2684 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
2 ms |
2644 KB |
Output is correct |
25 |
Correct |
2 ms |
2680 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2680 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
2 ms |
2644 KB |
Output is correct |
31 |
Correct |
2 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
3 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2628 KB |
Output is correct |
36 |
Correct |
4 ms |
2880 KB |
Output is correct |
37 |
Correct |
4 ms |
2900 KB |
Output is correct |
38 |
Correct |
3 ms |
2684 KB |
Output is correct |
39 |
Correct |
21 ms |
5868 KB |
Output is correct |
40 |
Correct |
8 ms |
3460 KB |
Output is correct |
41 |
Correct |
3 ms |
2644 KB |
Output is correct |
42 |
Correct |
10 ms |
3460 KB |
Output is correct |
43 |
Correct |
3 ms |
2772 KB |
Output is correct |
44 |
Correct |
3 ms |
2644 KB |
Output is correct |
45 |
Correct |
2 ms |
2644 KB |
Output is correct |
46 |
Correct |
30 ms |
6220 KB |
Output is correct |
47 |
Correct |
5 ms |
3076 KB |
Output is correct |
48 |
Correct |
20 ms |
5780 KB |
Output is correct |
49 |
Correct |
23 ms |
5948 KB |
Output is correct |
50 |
Correct |
3 ms |
2644 KB |
Output is correct |
51 |
Correct |
2 ms |
2684 KB |
Output is correct |
52 |
Correct |
2 ms |
2728 KB |
Output is correct |
53 |
Correct |
14 ms |
4356 KB |
Output is correct |
54 |
Correct |
23 ms |
5940 KB |
Output is correct |
55 |
Correct |
2 ms |
2680 KB |
Output is correct |
56 |
Correct |
2 ms |
2644 KB |
Output is correct |
57 |
Correct |
2 ms |
2644 KB |
Output is correct |
58 |
Correct |
31 ms |
6248 KB |
Output is correct |
59 |
Correct |
3 ms |
2680 KB |
Output is correct |
60 |
Correct |
3 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
7600 KB |
Output is correct |
2 |
Correct |
6 ms |
4052 KB |
Output is correct |
3 |
Correct |
1348 ms |
76436 KB |
Output is correct |
4 |
Correct |
622 ms |
48476 KB |
Output is correct |
5 |
Correct |
197 ms |
12392 KB |
Output is correct |
6 |
Correct |
189 ms |
10464 KB |
Output is correct |
7 |
Correct |
196 ms |
13436 KB |
Output is correct |
8 |
Correct |
61 ms |
7768 KB |
Output is correct |
9 |
Correct |
117 ms |
9876 KB |
Output is correct |
10 |
Correct |
88 ms |
8508 KB |
Output is correct |
11 |
Correct |
1342 ms |
70248 KB |
Output is correct |
12 |
Correct |
124 ms |
8884 KB |
Output is correct |
13 |
Correct |
407 ms |
31868 KB |
Output is correct |
14 |
Correct |
185 ms |
13872 KB |
Output is correct |
15 |
Correct |
1477 ms |
69332 KB |
Output is correct |
16 |
Correct |
57 ms |
7244 KB |
Output is correct |
17 |
Correct |
1041 ms |
51628 KB |
Output is correct |
18 |
Correct |
6 ms |
4308 KB |
Output is correct |
19 |
Correct |
1524 ms |
73564 KB |
Output is correct |
20 |
Correct |
188 ms |
13040 KB |
Output is correct |
21 |
Correct |
183 ms |
11796 KB |
Output is correct |
22 |
Correct |
94 ms |
8244 KB |
Output is correct |
23 |
Correct |
20 ms |
6384 KB |
Output is correct |
24 |
Correct |
977 ms |
56904 KB |
Output is correct |
25 |
Correct |
129 ms |
10028 KB |
Output is correct |
26 |
Correct |
76 ms |
7788 KB |
Output is correct |
27 |
Correct |
105 ms |
9104 KB |
Output is correct |
28 |
Correct |
13 ms |
5252 KB |
Output is correct |
29 |
Correct |
213 ms |
13124 KB |
Output is correct |
30 |
Correct |
352 ms |
23788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2684 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2680 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2680 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
3 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
3 ms |
2676 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2684 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
2 ms |
2644 KB |
Output is correct |
25 |
Correct |
2 ms |
2680 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2680 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
2 ms |
2644 KB |
Output is correct |
31 |
Correct |
2 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
3 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2628 KB |
Output is correct |
36 |
Correct |
4 ms |
2880 KB |
Output is correct |
37 |
Correct |
4 ms |
2900 KB |
Output is correct |
38 |
Correct |
3 ms |
2684 KB |
Output is correct |
39 |
Correct |
21 ms |
5868 KB |
Output is correct |
40 |
Correct |
8 ms |
3460 KB |
Output is correct |
41 |
Correct |
3 ms |
2644 KB |
Output is correct |
42 |
Correct |
10 ms |
3460 KB |
Output is correct |
43 |
Correct |
3 ms |
2772 KB |
Output is correct |
44 |
Correct |
3 ms |
2644 KB |
Output is correct |
45 |
Correct |
2 ms |
2644 KB |
Output is correct |
46 |
Correct |
30 ms |
6220 KB |
Output is correct |
47 |
Correct |
5 ms |
3076 KB |
Output is correct |
48 |
Correct |
20 ms |
5780 KB |
Output is correct |
49 |
Correct |
23 ms |
5948 KB |
Output is correct |
50 |
Correct |
3 ms |
2644 KB |
Output is correct |
51 |
Correct |
2 ms |
2684 KB |
Output is correct |
52 |
Correct |
2 ms |
2728 KB |
Output is correct |
53 |
Correct |
14 ms |
4356 KB |
Output is correct |
54 |
Correct |
23 ms |
5940 KB |
Output is correct |
55 |
Correct |
2 ms |
2680 KB |
Output is correct |
56 |
Correct |
2 ms |
2644 KB |
Output is correct |
57 |
Correct |
2 ms |
2644 KB |
Output is correct |
58 |
Correct |
31 ms |
6248 KB |
Output is correct |
59 |
Correct |
3 ms |
2680 KB |
Output is correct |
60 |
Correct |
3 ms |
2644 KB |
Output is correct |
61 |
Correct |
80 ms |
7600 KB |
Output is correct |
62 |
Correct |
6 ms |
4052 KB |
Output is correct |
63 |
Correct |
1348 ms |
76436 KB |
Output is correct |
64 |
Correct |
622 ms |
48476 KB |
Output is correct |
65 |
Correct |
197 ms |
12392 KB |
Output is correct |
66 |
Correct |
189 ms |
10464 KB |
Output is correct |
67 |
Correct |
196 ms |
13436 KB |
Output is correct |
68 |
Correct |
61 ms |
7768 KB |
Output is correct |
69 |
Correct |
117 ms |
9876 KB |
Output is correct |
70 |
Correct |
88 ms |
8508 KB |
Output is correct |
71 |
Correct |
1342 ms |
70248 KB |
Output is correct |
72 |
Correct |
124 ms |
8884 KB |
Output is correct |
73 |
Correct |
407 ms |
31868 KB |
Output is correct |
74 |
Correct |
185 ms |
13872 KB |
Output is correct |
75 |
Correct |
1477 ms |
69332 KB |
Output is correct |
76 |
Correct |
57 ms |
7244 KB |
Output is correct |
77 |
Correct |
1041 ms |
51628 KB |
Output is correct |
78 |
Correct |
6 ms |
4308 KB |
Output is correct |
79 |
Correct |
1524 ms |
73564 KB |
Output is correct |
80 |
Correct |
188 ms |
13040 KB |
Output is correct |
81 |
Correct |
183 ms |
11796 KB |
Output is correct |
82 |
Correct |
94 ms |
8244 KB |
Output is correct |
83 |
Correct |
20 ms |
6384 KB |
Output is correct |
84 |
Correct |
977 ms |
56904 KB |
Output is correct |
85 |
Correct |
129 ms |
10028 KB |
Output is correct |
86 |
Correct |
76 ms |
7788 KB |
Output is correct |
87 |
Correct |
105 ms |
9104 KB |
Output is correct |
88 |
Correct |
13 ms |
5252 KB |
Output is correct |
89 |
Correct |
213 ms |
13124 KB |
Output is correct |
90 |
Correct |
352 ms |
23788 KB |
Output is correct |
91 |
Correct |
188 ms |
9852 KB |
Output is correct |
92 |
Correct |
1672 ms |
86656 KB |
Output is correct |
93 |
Correct |
317 ms |
13812 KB |
Output is correct |
94 |
Correct |
1052 ms |
47652 KB |
Output is correct |
95 |
Correct |
7 ms |
4100 KB |
Output is correct |
96 |
Correct |
8 ms |
4396 KB |
Output is correct |
97 |
Correct |
314 ms |
18048 KB |
Output is correct |
98 |
Correct |
153 ms |
9704 KB |
Output is correct |
99 |
Correct |
145 ms |
10344 KB |
Output is correct |
100 |
Correct |
1884 ms |
94308 KB |
Output is correct |
101 |
Correct |
770 ms |
46260 KB |
Output is correct |
102 |
Correct |
758 ms |
46116 KB |
Output is correct |
103 |
Correct |
1099 ms |
59904 KB |
Output is correct |
104 |
Correct |
1385 ms |
71504 KB |
Output is correct |
105 |
Correct |
94 ms |
7896 KB |
Output is correct |
106 |
Correct |
1142 ms |
60460 KB |
Output is correct |
107 |
Correct |
470 ms |
26024 KB |
Output is correct |
108 |
Correct |
243 ms |
12864 KB |
Output is correct |
109 |
Correct |
17 ms |
5708 KB |
Output is correct |
110 |
Correct |
69 ms |
7400 KB |
Output is correct |
111 |
Correct |
237 ms |
13076 KB |
Output is correct |
112 |
Correct |
1683 ms |
96016 KB |
Output is correct |
113 |
Correct |
1809 ms |
97072 KB |
Output is correct |
114 |
Correct |
260 ms |
12592 KB |
Output is correct |
115 |
Correct |
722 ms |
45424 KB |
Output is correct |
116 |
Correct |
1764 ms |
84508 KB |
Output is correct |
117 |
Correct |
1257 ms |
58704 KB |
Output is correct |
118 |
Correct |
1187 ms |
52308 KB |
Output is correct |
119 |
Correct |
1657 ms |
73724 KB |
Output is correct |
120 |
Correct |
1141 ms |
41908 KB |
Output is correct |