#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int dist1[300005], dist2[300005], n, m, s, t, u, v;
vector <pi> adj[100005];
int brr[100005][4];
void dijk(int dist[], int ss){
for(int i = 1; i <= n; i++)dist[i] = 1e18;
dist[ss] = 0;
priority_queue <pi, vector <pi>, greater<pi> > pq;
pq.push({0, ss});
while(!pq.empty()){
int x = pq.top().fi, y = pq.top().se;
pq.pop();
if(dist[y] < x)continue;
for(auto [i, j] : adj[y]){
if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i});
}
}
}
void solve(){
cin >> n >> m >> s >> t >> u >> v;
while (m--){
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dijk(dist1, s);
dijk(dist2, t);
for(int i = 1; i <= n; i++)for(int j = 0; j < 4; j++)brr[i][j] = 1e18;
brr[u][0] = brr[u][1] = brr[u][2] = brr[u][3] = 0;
priority_queue <pii, vector<pii>, greater<pii> > pq;
pq.push({0, {u, 0}});
while(!pq.empty()){
int x = pq.top().fi, y = pq.top().se.fi, z = pq.top().se.se;
pq.pop();
if(brr[y][z] < x)continue;
for(auto [i, j] : adj[y]){
if(z == 0){
if(dist1[y] + dist2[i] + j == dist1[t]){
if(brr[i][1] > x)brr[i][1] = x, pq.push({brr[i][1], {i, 1}});
}
else if(dist1[i] + dist2[y] + j == dist1[t]){
if(brr[i][2] > x)brr[i][2] = x, pq.push({brr[i][2], {i, 2}});
}
if(brr[i][0] > x + j)brr[i][0] = x + j, pq.push({brr[i][0], {i, 0}});
}
else if(z == 1){
if(dist1[y] + j + dist2[i] == dist1[t]){
if(brr[i][1] > x)brr[i][1] = x, pq.push({brr[i][1], {i, 1}});
}
else{
if(brr[i][3] > x + j)brr[i][3] = x + j, pq.push({brr[i][3], {i, 3}});
}
}
else if(z == 2){
if(dist1[i] + dist2[y] + j == dist1[t]){
if(brr[i][2] > x)brr[i][2] = x, pq.push({brr[i][2], {i, 2}});
}
else{
if(brr[i][3] > x + j)pq.push({x + j, {i, 3}}), brr[i][3] = x + j;
}
}
else{
if(brr[i][3] > x + j)brr[i][3] = x + j, pq.push({brr[i][3], {i, 3}});
}
}
}
cout << min({brr[v][0], brr[v][1], brr[v][2], brr[v][3]});
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
83 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
293 ms |
27232 KB |
Output is correct |
2 |
Correct |
334 ms |
22612 KB |
Output is correct |
3 |
Correct |
385 ms |
23884 KB |
Output is correct |
4 |
Correct |
307 ms |
22408 KB |
Output is correct |
5 |
Correct |
351 ms |
22432 KB |
Output is correct |
6 |
Correct |
295 ms |
27068 KB |
Output is correct |
7 |
Correct |
349 ms |
22440 KB |
Output is correct |
8 |
Correct |
344 ms |
22376 KB |
Output is correct |
9 |
Correct |
301 ms |
22504 KB |
Output is correct |
10 |
Correct |
255 ms |
22448 KB |
Output is correct |
11 |
Correct |
131 ms |
14452 KB |
Output is correct |
12 |
Correct |
342 ms |
22456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
22672 KB |
Output is correct |
2 |
Correct |
369 ms |
22704 KB |
Output is correct |
3 |
Correct |
366 ms |
22556 KB |
Output is correct |
4 |
Correct |
340 ms |
22436 KB |
Output is correct |
5 |
Correct |
369 ms |
22544 KB |
Output is correct |
6 |
Correct |
342 ms |
22448 KB |
Output is correct |
7 |
Correct |
383 ms |
25540 KB |
Output is correct |
8 |
Correct |
363 ms |
23456 KB |
Output is correct |
9 |
Correct |
367 ms |
23500 KB |
Output is correct |
10 |
Correct |
361 ms |
23548 KB |
Output is correct |
11 |
Correct |
170 ms |
15432 KB |
Output is correct |
12 |
Correct |
339 ms |
23504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4052 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2692 KB |
Output is correct |
4 |
Correct |
15 ms |
5484 KB |
Output is correct |
5 |
Correct |
8 ms |
4100 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
3 ms |
2852 KB |
Output is correct |
8 |
Correct |
3 ms |
2900 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
9 ms |
4036 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 |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
293 ms |
27232 KB |
Output is correct |
2 |
Correct |
334 ms |
22612 KB |
Output is correct |
3 |
Correct |
385 ms |
23884 KB |
Output is correct |
4 |
Correct |
307 ms |
22408 KB |
Output is correct |
5 |
Correct |
351 ms |
22432 KB |
Output is correct |
6 |
Correct |
295 ms |
27068 KB |
Output is correct |
7 |
Correct |
349 ms |
22440 KB |
Output is correct |
8 |
Correct |
344 ms |
22376 KB |
Output is correct |
9 |
Correct |
301 ms |
22504 KB |
Output is correct |
10 |
Correct |
255 ms |
22448 KB |
Output is correct |
11 |
Correct |
131 ms |
14452 KB |
Output is correct |
12 |
Correct |
342 ms |
22456 KB |
Output is correct |
13 |
Correct |
362 ms |
22672 KB |
Output is correct |
14 |
Correct |
369 ms |
22704 KB |
Output is correct |
15 |
Correct |
366 ms |
22556 KB |
Output is correct |
16 |
Correct |
340 ms |
22436 KB |
Output is correct |
17 |
Correct |
369 ms |
22544 KB |
Output is correct |
18 |
Correct |
342 ms |
22448 KB |
Output is correct |
19 |
Correct |
383 ms |
25540 KB |
Output is correct |
20 |
Correct |
363 ms |
23456 KB |
Output is correct |
21 |
Correct |
367 ms |
23500 KB |
Output is correct |
22 |
Correct |
361 ms |
23548 KB |
Output is correct |
23 |
Correct |
170 ms |
15432 KB |
Output is correct |
24 |
Correct |
339 ms |
23504 KB |
Output is correct |
25 |
Correct |
8 ms |
4052 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2692 KB |
Output is correct |
28 |
Correct |
15 ms |
5484 KB |
Output is correct |
29 |
Correct |
8 ms |
4100 KB |
Output is correct |
30 |
Correct |
2 ms |
2772 KB |
Output is correct |
31 |
Correct |
3 ms |
2852 KB |
Output is correct |
32 |
Correct |
3 ms |
2900 KB |
Output is correct |
33 |
Correct |
2 ms |
2772 KB |
Output is correct |
34 |
Correct |
9 ms |
4036 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
2 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
2 ms |
2772 KB |
Output is correct |
39 |
Correct |
2 ms |
2772 KB |
Output is correct |
40 |
Correct |
281 ms |
27208 KB |
Output is correct |
41 |
Correct |
295 ms |
21716 KB |
Output is correct |
42 |
Correct |
314 ms |
21708 KB |
Output is correct |
43 |
Correct |
179 ms |
15360 KB |
Output is correct |
44 |
Correct |
166 ms |
15360 KB |
Output is correct |
45 |
Correct |
356 ms |
23424 KB |
Output is correct |
46 |
Correct |
347 ms |
23528 KB |
Output is correct |
47 |
Correct |
285 ms |
24836 KB |
Output is correct |
48 |
Correct |
165 ms |
15372 KB |
Output is correct |
49 |
Correct |
270 ms |
27132 KB |
Output is correct |
50 |
Correct |
354 ms |
26592 KB |
Output is correct |
51 |
Correct |
393 ms |
26516 KB |
Output is correct |