#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
ll n, m, S, T, U, V, a, b, c, dist[NMAX], ans, cost[NMAX], C1[NMAX], C2[NMAX], vis[NMAX];
vector<pair<int, ll>> adj[NMAX];
void dijk(int s){
memset(dist, 0x3f, sizeof(dist));
priority_queue<pair<ll, ll>> pq;
pq.emplace(0, s); dist[s] = 0;
while(pq.size()){
auto[d, x] = pq.top(); pq.pop();
d = -d;
if(d > dist[x]) continue;
for(auto&[nx, p] : adj[x])
if(d + p < dist[nx]){
dist[nx] = d + p;
pq.emplace(-d-p, nx);
}
}
return;
}
void go(int s, int t){
dijk(s);
priority_queue<pair<ll, ll>> pq;
memset(vis, 0, sizeof(vis));
pq.emplace(dist[t], t); vis[t] = 1;
while(pq.size()){
auto[d, x] = pq.top(); pq.pop();
for(auto&[nx, p]: adj[x])
if(d - p == dist[nx]){
C1[nx] = min(C1[nx], C1[x]);
if(!vis[nx]) vis[nx] = 1, pq.emplace(d-p, nx);
}
}
return;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> S >> T >> U >> V;
while(m--){
cin >> a >> b >> c;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
dijk(U);
for(int i = 1; i <= n; i++) C1[i] = C2[i] = dist[i];
ans = dist[V];
go(S, T);
swap(C1, C2);
go(T, S);
for(int i = 1; i <= n; i++) cost[i] = min(C1[i], C2[i]);
dijk(V);
for(int i = 1; i <= n; i++) ans = min(ans, dist[i] + cost[i]);
cout << ans;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijk(int)':
commuter_pass.cpp:16:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
16 | auto[d, x] = pq.top(); pq.pop();
| ^
commuter_pass.cpp:19:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for(auto&[nx, p] : adj[x])
| ^
commuter_pass.cpp: In function 'void go(int, int)':
commuter_pass.cpp:34:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | auto[d, x] = pq.top(); pq.pop();
| ^
commuter_pass.cpp:35:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
35 | for(auto&[nx, p]: adj[x])
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
20612 KB |
Output is correct |
2 |
Correct |
268 ms |
19056 KB |
Output is correct |
3 |
Correct |
275 ms |
22976 KB |
Output is correct |
4 |
Correct |
236 ms |
23748 KB |
Output is correct |
5 |
Correct |
274 ms |
22116 KB |
Output is correct |
6 |
Correct |
241 ms |
23996 KB |
Output is correct |
7 |
Correct |
268 ms |
22200 KB |
Output is correct |
8 |
Correct |
233 ms |
22276 KB |
Output is correct |
9 |
Correct |
196 ms |
23012 KB |
Output is correct |
10 |
Correct |
156 ms |
22964 KB |
Output is correct |
11 |
Correct |
70 ms |
13832 KB |
Output is correct |
12 |
Correct |
205 ms |
23004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
19372 KB |
Output is correct |
2 |
Correct |
222 ms |
19232 KB |
Output is correct |
3 |
Correct |
216 ms |
19076 KB |
Output is correct |
4 |
Correct |
266 ms |
19032 KB |
Output is correct |
5 |
Correct |
221 ms |
19080 KB |
Output is correct |
6 |
Correct |
207 ms |
18972 KB |
Output is correct |
7 |
Correct |
221 ms |
19072 KB |
Output is correct |
8 |
Correct |
274 ms |
19148 KB |
Output is correct |
9 |
Correct |
209 ms |
19072 KB |
Output is correct |
10 |
Correct |
227 ms |
19116 KB |
Output is correct |
11 |
Correct |
69 ms |
12024 KB |
Output is correct |
12 |
Correct |
213 ms |
18952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7524 KB |
Output is correct |
2 |
Correct |
3 ms |
5768 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Correct |
13 ms |
9296 KB |
Output is correct |
5 |
Correct |
8 ms |
7424 KB |
Output is correct |
6 |
Correct |
4 ms |
5844 KB |
Output is correct |
7 |
Correct |
4 ms |
5892 KB |
Output is correct |
8 |
Correct |
4 ms |
5972 KB |
Output is correct |
9 |
Correct |
4 ms |
5844 KB |
Output is correct |
10 |
Correct |
8 ms |
7432 KB |
Output is correct |
11 |
Correct |
3 ms |
5716 KB |
Output is correct |
12 |
Correct |
4 ms |
5760 KB |
Output is correct |
13 |
Correct |
4 ms |
5844 KB |
Output is correct |
14 |
Correct |
3 ms |
5844 KB |
Output is correct |
15 |
Correct |
5 ms |
5844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
20612 KB |
Output is correct |
2 |
Correct |
268 ms |
19056 KB |
Output is correct |
3 |
Correct |
275 ms |
22976 KB |
Output is correct |
4 |
Correct |
236 ms |
23748 KB |
Output is correct |
5 |
Correct |
274 ms |
22116 KB |
Output is correct |
6 |
Correct |
241 ms |
23996 KB |
Output is correct |
7 |
Correct |
268 ms |
22200 KB |
Output is correct |
8 |
Correct |
233 ms |
22276 KB |
Output is correct |
9 |
Correct |
196 ms |
23012 KB |
Output is correct |
10 |
Correct |
156 ms |
22964 KB |
Output is correct |
11 |
Correct |
70 ms |
13832 KB |
Output is correct |
12 |
Correct |
205 ms |
23004 KB |
Output is correct |
13 |
Correct |
207 ms |
19372 KB |
Output is correct |
14 |
Correct |
222 ms |
19232 KB |
Output is correct |
15 |
Correct |
216 ms |
19076 KB |
Output is correct |
16 |
Correct |
266 ms |
19032 KB |
Output is correct |
17 |
Correct |
221 ms |
19080 KB |
Output is correct |
18 |
Correct |
207 ms |
18972 KB |
Output is correct |
19 |
Correct |
221 ms |
19072 KB |
Output is correct |
20 |
Correct |
274 ms |
19148 KB |
Output is correct |
21 |
Correct |
209 ms |
19072 KB |
Output is correct |
22 |
Correct |
227 ms |
19116 KB |
Output is correct |
23 |
Correct |
69 ms |
12024 KB |
Output is correct |
24 |
Correct |
213 ms |
18952 KB |
Output is correct |
25 |
Correct |
8 ms |
7524 KB |
Output is correct |
26 |
Correct |
3 ms |
5768 KB |
Output is correct |
27 |
Correct |
3 ms |
5844 KB |
Output is correct |
28 |
Correct |
13 ms |
9296 KB |
Output is correct |
29 |
Correct |
8 ms |
7424 KB |
Output is correct |
30 |
Correct |
4 ms |
5844 KB |
Output is correct |
31 |
Correct |
4 ms |
5892 KB |
Output is correct |
32 |
Correct |
4 ms |
5972 KB |
Output is correct |
33 |
Correct |
4 ms |
5844 KB |
Output is correct |
34 |
Correct |
8 ms |
7432 KB |
Output is correct |
35 |
Correct |
3 ms |
5716 KB |
Output is correct |
36 |
Correct |
4 ms |
5760 KB |
Output is correct |
37 |
Correct |
4 ms |
5844 KB |
Output is correct |
38 |
Correct |
3 ms |
5844 KB |
Output is correct |
39 |
Correct |
5 ms |
5844 KB |
Output is correct |
40 |
Correct |
179 ms |
23800 KB |
Output is correct |
41 |
Correct |
201 ms |
22916 KB |
Output is correct |
42 |
Correct |
214 ms |
23100 KB |
Output is correct |
43 |
Correct |
101 ms |
13828 KB |
Output is correct |
44 |
Correct |
72 ms |
13876 KB |
Output is correct |
45 |
Correct |
237 ms |
21260 KB |
Output is correct |
46 |
Correct |
240 ms |
21636 KB |
Output is correct |
47 |
Correct |
193 ms |
23736 KB |
Output is correct |
48 |
Correct |
89 ms |
13352 KB |
Output is correct |
49 |
Correct |
154 ms |
23492 KB |
Output is correct |
50 |
Correct |
214 ms |
22040 KB |
Output is correct |
51 |
Correct |
279 ms |
21812 KB |
Output is correct |