#include <bits/stdc++.h>
using namespace std;
#define long long long
#define pli pair<long, int>
#define pii pair<int, int>
#define x first
#define y second
const int N = 1e5+5;
int n, m, s, t, u, v;
long d[3][N], z[4][N];
bool mark[N];
vector<pii> g[N];
void dijkstra(int u, long d[]) {
fill_n(d, N, (long)1e18);
priority_queue<pli, vector<pli>, greater<pli> > Q;
Q.emplace(d[u] = 0, u);
while(!Q.empty()) {
auto u = Q.top(); Q.pop();
if(mark[u.y]) continue;
else mark[u.y] = true;
for(auto v : g[u.y]) if(d[v.x] > u.x + v.y) {
Q.emplace(d[v.x] = u.x + v.y, v.x);
}
}
memset(mark, 0, sizeof mark);
}
int main() {
scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v );
for(int i = 0, u, v, w; i < m; ++i) {
scanf("%d %d %d", &u, &v, &w);
g[u].emplace_back(v, w), g[v].emplace_back(u, w);
}
dijkstra(u, d[1]), dijkstra(v, d[2]), dijkstra(s, d[0]);
long mn = 1e18;
for(int i = 1; i <= n; ++i) z[1][i] = d[1][i], z[2][i] = d[2][i], z[3][i] = d[1][i] + d[2][i], mn = min(mn, z[3][i]);
fill_n(z[0], N, (long)1e18);
priority_queue<pli, vector<pli>, greater<pli> > Q;
Q.emplace(z[0][s] = 0, s);
while(!Q.empty()) {
auto u = Q.top(); Q.pop();
for(auto v : g[u.y]) if(u.x + v.y == d[0][v.x]) {
if(!mark[v.x]) mark[v.x] = true, Q.emplace(z[0][v.x] = u.x + v.y, v.x);
z[1][v.x] = min(z[1][v.x], z[1][u.y]);
z[2][v.x] = min(z[2][v.x], z[2][u.y]);
z[3][v.x] = min({z[3][v.x], z[1][u.y] + d[2][v.x], z[2][u.y] + d[1][v.x], z[3][u.y]});
}
}
return !printf("%lld\n", min(mn, z[3][t]));
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v );
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
615 ms |
20028 KB |
Output is correct |
2 |
Correct |
556 ms |
22492 KB |
Output is correct |
3 |
Correct |
521 ms |
25928 KB |
Output is correct |
4 |
Correct |
514 ms |
31460 KB |
Output is correct |
5 |
Correct |
540 ms |
34000 KB |
Output is correct |
6 |
Correct |
522 ms |
38612 KB |
Output is correct |
7 |
Correct |
463 ms |
40824 KB |
Output is correct |
8 |
Correct |
477 ms |
44416 KB |
Output is correct |
9 |
Correct |
532 ms |
49132 KB |
Output is correct |
10 |
Correct |
478 ms |
54484 KB |
Output is correct |
11 |
Correct |
263 ms |
54484 KB |
Output is correct |
12 |
Correct |
569 ms |
59600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
643 ms |
63488 KB |
Output is correct |
2 |
Correct |
536 ms |
66232 KB |
Output is correct |
3 |
Correct |
537 ms |
69724 KB |
Output is correct |
4 |
Correct |
510 ms |
73276 KB |
Output is correct |
5 |
Correct |
484 ms |
76724 KB |
Output is correct |
6 |
Correct |
490 ms |
77488 KB |
Output is correct |
7 |
Correct |
573 ms |
77488 KB |
Output is correct |
8 |
Correct |
560 ms |
77488 KB |
Output is correct |
9 |
Correct |
447 ms |
77564 KB |
Output is correct |
10 |
Correct |
553 ms |
77728 KB |
Output is correct |
11 |
Correct |
271 ms |
77728 KB |
Output is correct |
12 |
Correct |
411 ms |
77728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
77728 KB |
Output is correct |
2 |
Correct |
9 ms |
77728 KB |
Output is correct |
3 |
Correct |
9 ms |
77728 KB |
Output is correct |
4 |
Correct |
30 ms |
77728 KB |
Output is correct |
5 |
Correct |
17 ms |
77728 KB |
Output is correct |
6 |
Correct |
8 ms |
77728 KB |
Output is correct |
7 |
Correct |
8 ms |
77728 KB |
Output is correct |
8 |
Correct |
11 ms |
77728 KB |
Output is correct |
9 |
Correct |
11 ms |
77728 KB |
Output is correct |
10 |
Correct |
18 ms |
77728 KB |
Output is correct |
11 |
Correct |
9 ms |
77728 KB |
Output is correct |
12 |
Correct |
9 ms |
77728 KB |
Output is correct |
13 |
Correct |
8 ms |
77728 KB |
Output is correct |
14 |
Correct |
9 ms |
77728 KB |
Output is correct |
15 |
Correct |
9 ms |
77728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
615 ms |
20028 KB |
Output is correct |
2 |
Correct |
556 ms |
22492 KB |
Output is correct |
3 |
Correct |
521 ms |
25928 KB |
Output is correct |
4 |
Correct |
514 ms |
31460 KB |
Output is correct |
5 |
Correct |
540 ms |
34000 KB |
Output is correct |
6 |
Correct |
522 ms |
38612 KB |
Output is correct |
7 |
Correct |
463 ms |
40824 KB |
Output is correct |
8 |
Correct |
477 ms |
44416 KB |
Output is correct |
9 |
Correct |
532 ms |
49132 KB |
Output is correct |
10 |
Correct |
478 ms |
54484 KB |
Output is correct |
11 |
Correct |
263 ms |
54484 KB |
Output is correct |
12 |
Correct |
569 ms |
59600 KB |
Output is correct |
13 |
Correct |
643 ms |
63488 KB |
Output is correct |
14 |
Correct |
536 ms |
66232 KB |
Output is correct |
15 |
Correct |
537 ms |
69724 KB |
Output is correct |
16 |
Correct |
510 ms |
73276 KB |
Output is correct |
17 |
Correct |
484 ms |
76724 KB |
Output is correct |
18 |
Correct |
490 ms |
77488 KB |
Output is correct |
19 |
Correct |
573 ms |
77488 KB |
Output is correct |
20 |
Correct |
560 ms |
77488 KB |
Output is correct |
21 |
Correct |
447 ms |
77564 KB |
Output is correct |
22 |
Correct |
553 ms |
77728 KB |
Output is correct |
23 |
Correct |
271 ms |
77728 KB |
Output is correct |
24 |
Correct |
411 ms |
77728 KB |
Output is correct |
25 |
Correct |
25 ms |
77728 KB |
Output is correct |
26 |
Correct |
9 ms |
77728 KB |
Output is correct |
27 |
Correct |
9 ms |
77728 KB |
Output is correct |
28 |
Correct |
30 ms |
77728 KB |
Output is correct |
29 |
Correct |
17 ms |
77728 KB |
Output is correct |
30 |
Correct |
8 ms |
77728 KB |
Output is correct |
31 |
Correct |
8 ms |
77728 KB |
Output is correct |
32 |
Correct |
11 ms |
77728 KB |
Output is correct |
33 |
Correct |
11 ms |
77728 KB |
Output is correct |
34 |
Correct |
18 ms |
77728 KB |
Output is correct |
35 |
Correct |
9 ms |
77728 KB |
Output is correct |
36 |
Correct |
9 ms |
77728 KB |
Output is correct |
37 |
Correct |
8 ms |
77728 KB |
Output is correct |
38 |
Correct |
9 ms |
77728 KB |
Output is correct |
39 |
Correct |
9 ms |
77728 KB |
Output is correct |
40 |
Correct |
505 ms |
84872 KB |
Output is correct |
41 |
Correct |
504 ms |
87576 KB |
Output is correct |
42 |
Correct |
447 ms |
91768 KB |
Output is correct |
43 |
Correct |
210 ms |
91768 KB |
Output is correct |
44 |
Correct |
279 ms |
91872 KB |
Output is correct |
45 |
Correct |
458 ms |
100136 KB |
Output is correct |
46 |
Correct |
573 ms |
103224 KB |
Output is correct |
47 |
Correct |
582 ms |
107276 KB |
Output is correct |
48 |
Correct |
280 ms |
107276 KB |
Output is correct |
49 |
Correct |
435 ms |
114036 KB |
Output is correct |
50 |
Correct |
517 ms |
115824 KB |
Output is correct |
51 |
Correct |
481 ms |
119276 KB |
Output is correct |