#include <bits/stdc++.h>
using namespace std;
#define MX 100100
#define ll long long
#define x first
#define y second
int N, M, S, T, U, V;
ll dis[3][MX], best[4][MX];
bool vis[MX];
vector<pair<int, int>> adj[MX];
vector<int> par[MX], nxt[MX], prv[MX], v;
void dij(int s, int z) {
priority_queue<pair<ll, pair<int, int>>> q;
q.push({0, {s, 0}});
while (q.size()) {
pair<ll, pair<int, int>> cur = q.top(); q.pop();
if (!z && cur.y.y && (!vis[cur.y.x] || dis[z][cur.y.x] == -cur.x)) {
par[cur.y.x].push_back(cur.y.y);
}
if (vis[cur.y.x]) continue;
vis[cur.y.x] = 1;
dis[z][cur.y.x] = -cur.x;
for (pair<int, int> i : adj[cur.y.x]) {
q.push({cur.x-i.y, {i.x, cur.y.x}});
}
}
for (int i = 1; i <= N; i++) vis[i] = 0;
}
void dfs(int n) {
if (vis[n]) return;
vis[n] = 1;
for (int i : par[n]) {
nxt[i].push_back(n);
prv[n].push_back(i);
dfs(i);
}
v.push_back(n);
}
int main() {
scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
for (int i = 0, A, B, C; i < M; i++) {
scanf("%d%d%d", &A, &B, &C);
adj[A].push_back({B, C});
adj[B].push_back({A, C});
}
dij(S, 0); dij(U, 1); dij(V, 2); dfs(T);
for (int i = 0; i < 4; i++)
for (int j = 1; j <= N; j++)
best[i][j] = 1e16;
for (int _ = 0; _ < 2; _++) {
for (int i : v) {
for (int k = 2*_; k < 2*_+2; k++) {
best[k][i] = dis[(k&1)+1][i];
for (int j : prv[i]) {
best[k][i] = min(best[k][i], best[k][j]);
}
}
}
reverse(v.begin(), v.end());
}
ll ans = dis[1][V];
for (int i = 1; i <= N; i++) {
ans = min({ans, best[0][i]+best[3][i], best[1][i]+best[2][i]});
}
printf("%lld\n", ans);
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:7: 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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &A, &B, &C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
}
^
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:72:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:45:5: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
int main() {
^~~~
commuter_pass.cpp:45:5: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
commuter_pass.cpp:45:5: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
630 ms |
28000 KB |
Output is correct |
2 |
Correct |
582 ms |
27480 KB |
Output is correct |
3 |
Correct |
648 ms |
33300 KB |
Output is correct |
4 |
Correct |
598 ms |
27424 KB |
Output is correct |
5 |
Correct |
743 ms |
27816 KB |
Output is correct |
6 |
Correct |
682 ms |
27784 KB |
Output is correct |
7 |
Correct |
709 ms |
28820 KB |
Output is correct |
8 |
Correct |
632 ms |
27920 KB |
Output is correct |
9 |
Correct |
674 ms |
27944 KB |
Output is correct |
10 |
Correct |
607 ms |
27852 KB |
Output is correct |
11 |
Correct |
260 ms |
27148 KB |
Output is correct |
12 |
Correct |
648 ms |
28184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
646 ms |
28048 KB |
Output is correct |
2 |
Correct |
619 ms |
30220 KB |
Output is correct |
3 |
Correct |
621 ms |
27776 KB |
Output is correct |
4 |
Correct |
590 ms |
28380 KB |
Output is correct |
5 |
Correct |
652 ms |
29264 KB |
Output is correct |
6 |
Correct |
667 ms |
32444 KB |
Output is correct |
7 |
Correct |
676 ms |
33380 KB |
Output is correct |
8 |
Correct |
642 ms |
28520 KB |
Output is correct |
9 |
Correct |
629 ms |
29340 KB |
Output is correct |
10 |
Correct |
610 ms |
27932 KB |
Output is correct |
11 |
Correct |
301 ms |
29812 KB |
Output is correct |
12 |
Correct |
657 ms |
32884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
11312 KB |
Output is correct |
2 |
Correct |
12 ms |
9856 KB |
Output is correct |
3 |
Correct |
13 ms |
9856 KB |
Output is correct |
4 |
Correct |
81 ms |
12948 KB |
Output is correct |
5 |
Correct |
46 ms |
12108 KB |
Output is correct |
6 |
Correct |
15 ms |
9984 KB |
Output is correct |
7 |
Correct |
14 ms |
9984 KB |
Output is correct |
8 |
Correct |
15 ms |
9984 KB |
Output is correct |
9 |
Correct |
13 ms |
9828 KB |
Output is correct |
10 |
Correct |
42 ms |
12192 KB |
Output is correct |
11 |
Correct |
11 ms |
9856 KB |
Output is correct |
12 |
Correct |
12 ms |
9728 KB |
Output is correct |
13 |
Correct |
12 ms |
9856 KB |
Output is correct |
14 |
Correct |
12 ms |
9856 KB |
Output is correct |
15 |
Correct |
12 ms |
9856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
630 ms |
28000 KB |
Output is correct |
2 |
Correct |
582 ms |
27480 KB |
Output is correct |
3 |
Correct |
648 ms |
33300 KB |
Output is correct |
4 |
Correct |
598 ms |
27424 KB |
Output is correct |
5 |
Correct |
743 ms |
27816 KB |
Output is correct |
6 |
Correct |
682 ms |
27784 KB |
Output is correct |
7 |
Correct |
709 ms |
28820 KB |
Output is correct |
8 |
Correct |
632 ms |
27920 KB |
Output is correct |
9 |
Correct |
674 ms |
27944 KB |
Output is correct |
10 |
Correct |
607 ms |
27852 KB |
Output is correct |
11 |
Correct |
260 ms |
27148 KB |
Output is correct |
12 |
Correct |
648 ms |
28184 KB |
Output is correct |
13 |
Correct |
646 ms |
28048 KB |
Output is correct |
14 |
Correct |
619 ms |
30220 KB |
Output is correct |
15 |
Correct |
621 ms |
27776 KB |
Output is correct |
16 |
Correct |
590 ms |
28380 KB |
Output is correct |
17 |
Correct |
652 ms |
29264 KB |
Output is correct |
18 |
Correct |
667 ms |
32444 KB |
Output is correct |
19 |
Correct |
676 ms |
33380 KB |
Output is correct |
20 |
Correct |
642 ms |
28520 KB |
Output is correct |
21 |
Correct |
629 ms |
29340 KB |
Output is correct |
22 |
Correct |
610 ms |
27932 KB |
Output is correct |
23 |
Correct |
301 ms |
29812 KB |
Output is correct |
24 |
Correct |
657 ms |
32884 KB |
Output is correct |
25 |
Correct |
51 ms |
11312 KB |
Output is correct |
26 |
Correct |
12 ms |
9856 KB |
Output is correct |
27 |
Correct |
13 ms |
9856 KB |
Output is correct |
28 |
Correct |
81 ms |
12948 KB |
Output is correct |
29 |
Correct |
46 ms |
12108 KB |
Output is correct |
30 |
Correct |
15 ms |
9984 KB |
Output is correct |
31 |
Correct |
14 ms |
9984 KB |
Output is correct |
32 |
Correct |
15 ms |
9984 KB |
Output is correct |
33 |
Correct |
13 ms |
9828 KB |
Output is correct |
34 |
Correct |
42 ms |
12192 KB |
Output is correct |
35 |
Correct |
11 ms |
9856 KB |
Output is correct |
36 |
Correct |
12 ms |
9728 KB |
Output is correct |
37 |
Correct |
12 ms |
9856 KB |
Output is correct |
38 |
Correct |
12 ms |
9856 KB |
Output is correct |
39 |
Correct |
12 ms |
9856 KB |
Output is correct |
40 |
Correct |
677 ms |
28112 KB |
Output is correct |
41 |
Correct |
609 ms |
27924 KB |
Output is correct |
42 |
Correct |
610 ms |
27932 KB |
Output is correct |
43 |
Correct |
314 ms |
31728 KB |
Output is correct |
44 |
Correct |
398 ms |
31728 KB |
Output is correct |
45 |
Correct |
702 ms |
31344 KB |
Output is correct |
46 |
Correct |
705 ms |
31392 KB |
Output is correct |
47 |
Correct |
728 ms |
25432 KB |
Output is correct |
48 |
Correct |
338 ms |
29808 KB |
Output is correct |
49 |
Correct |
627 ms |
27480 KB |
Output is correct |
50 |
Correct |
704 ms |
30020 KB |
Output is correct |
51 |
Correct |
789 ms |
31520 KB |
Output is correct |