#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define eb emplace_back
#define pb push_back
using namespace std;
using ll = long long;
using pii = pair<ll, int>;
using vi = vector<int>;
const int MN = 1e5 + 5;
int N, M, S, T, A, B; // stab O_O
vector<pii> g[MN];
ll disA[MN], disB[MN], disS[MN], disT[MN];
ll dp[MN][4];
void dijk(ll *dis, int st) {
for (int i = 1; i <= N; i++) dis[i] = 1e18;
dis[st] = 0;
priority_queue<pii, vector<pii>, greater<>> q;
q.emplace(0, st);
while (!q.empty()) {
auto [d, u] = q.top(); q.pop();
if (d > dis[u]) continue;
for (auto [v, w] : g[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.emplace(dis[v], v);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M >> S >> T >> A >> B;
for (int i = 0; i < M; i++) {
int u, v, w; cin >> u >> v >> w;
g[u].eb(v, w), g[v].eb(u, w);
}
dijk(disS, S), dijk(disT, T), dijk(disA, A), dijk(disB, B);
vector<pii> v;
for (int i = 1; i <= N; i++) {
v.eb(disS[i], i);
for (int j = 0; j <= 3; j++) dp[i][j] = 1e18;
}
sort(all(v));
ll mn = disS[T], ans = disA[B];
for (auto [d, u] : v) {
dp[u][1] = min(dp[u][1], disA[u]);
dp[u][2] = min(dp[u][2], disB[u]);
for (auto [v, w] : g[u]) {
if (d + w + disT[v] == mn) {
dp[v][1] = min(dp[v][1], dp[u][1]);
dp[v][2] = min(dp[v][2], dp[u][2]);
dp[v][3] = min(dp[v][3], dp[v][1] + disB[v]);
dp[v][3] = min(dp[v][3], dp[v][2] + disA[v]);
ans = min(ans, dp[v][3]);
}
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
384 ms |
23032 KB |
Output is correct |
2 |
Correct |
369 ms |
24840 KB |
Output is correct |
3 |
Correct |
449 ms |
26716 KB |
Output is correct |
4 |
Correct |
353 ms |
26844 KB |
Output is correct |
5 |
Correct |
420 ms |
24980 KB |
Output is correct |
6 |
Correct |
397 ms |
26876 KB |
Output is correct |
7 |
Correct |
378 ms |
24820 KB |
Output is correct |
8 |
Correct |
363 ms |
24788 KB |
Output is correct |
9 |
Correct |
368 ms |
25712 KB |
Output is correct |
10 |
Correct |
339 ms |
25804 KB |
Output is correct |
11 |
Correct |
160 ms |
18012 KB |
Output is correct |
12 |
Correct |
391 ms |
25716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
402 ms |
21572 KB |
Output is correct |
2 |
Correct |
391 ms |
24816 KB |
Output is correct |
3 |
Correct |
442 ms |
25092 KB |
Output is correct |
4 |
Correct |
402 ms |
24952 KB |
Output is correct |
5 |
Correct |
425 ms |
25044 KB |
Output is correct |
6 |
Correct |
332 ms |
25004 KB |
Output is correct |
7 |
Correct |
390 ms |
24824 KB |
Output is correct |
8 |
Correct |
374 ms |
24856 KB |
Output is correct |
9 |
Correct |
440 ms |
24956 KB |
Output is correct |
10 |
Correct |
363 ms |
24988 KB |
Output is correct |
11 |
Correct |
153 ms |
18012 KB |
Output is correct |
12 |
Correct |
424 ms |
25152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
4076 KB |
Output is correct |
2 |
Correct |
4 ms |
2796 KB |
Output is correct |
3 |
Correct |
3 ms |
2796 KB |
Output is correct |
4 |
Correct |
20 ms |
6252 KB |
Output is correct |
5 |
Correct |
11 ms |
4460 KB |
Output is correct |
6 |
Correct |
3 ms |
2796 KB |
Output is correct |
7 |
Correct |
3 ms |
2924 KB |
Output is correct |
8 |
Correct |
4 ms |
3052 KB |
Output is correct |
9 |
Correct |
3 ms |
2944 KB |
Output is correct |
10 |
Correct |
11 ms |
4460 KB |
Output is correct |
11 |
Correct |
2 ms |
2796 KB |
Output is correct |
12 |
Correct |
4 ms |
2944 KB |
Output is correct |
13 |
Correct |
3 ms |
2796 KB |
Output is correct |
14 |
Correct |
4 ms |
2944 KB |
Output is correct |
15 |
Correct |
4 ms |
2796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
384 ms |
23032 KB |
Output is correct |
2 |
Correct |
369 ms |
24840 KB |
Output is correct |
3 |
Correct |
449 ms |
26716 KB |
Output is correct |
4 |
Correct |
353 ms |
26844 KB |
Output is correct |
5 |
Correct |
420 ms |
24980 KB |
Output is correct |
6 |
Correct |
397 ms |
26876 KB |
Output is correct |
7 |
Correct |
378 ms |
24820 KB |
Output is correct |
8 |
Correct |
363 ms |
24788 KB |
Output is correct |
9 |
Correct |
368 ms |
25712 KB |
Output is correct |
10 |
Correct |
339 ms |
25804 KB |
Output is correct |
11 |
Correct |
160 ms |
18012 KB |
Output is correct |
12 |
Correct |
391 ms |
25716 KB |
Output is correct |
13 |
Correct |
402 ms |
21572 KB |
Output is correct |
14 |
Correct |
391 ms |
24816 KB |
Output is correct |
15 |
Correct |
442 ms |
25092 KB |
Output is correct |
16 |
Correct |
402 ms |
24952 KB |
Output is correct |
17 |
Correct |
425 ms |
25044 KB |
Output is correct |
18 |
Correct |
332 ms |
25004 KB |
Output is correct |
19 |
Correct |
390 ms |
24824 KB |
Output is correct |
20 |
Correct |
374 ms |
24856 KB |
Output is correct |
21 |
Correct |
440 ms |
24956 KB |
Output is correct |
22 |
Correct |
363 ms |
24988 KB |
Output is correct |
23 |
Correct |
153 ms |
18012 KB |
Output is correct |
24 |
Correct |
424 ms |
25152 KB |
Output is correct |
25 |
Correct |
11 ms |
4076 KB |
Output is correct |
26 |
Correct |
4 ms |
2796 KB |
Output is correct |
27 |
Correct |
3 ms |
2796 KB |
Output is correct |
28 |
Correct |
20 ms |
6252 KB |
Output is correct |
29 |
Correct |
11 ms |
4460 KB |
Output is correct |
30 |
Correct |
3 ms |
2796 KB |
Output is correct |
31 |
Correct |
3 ms |
2924 KB |
Output is correct |
32 |
Correct |
4 ms |
3052 KB |
Output is correct |
33 |
Correct |
3 ms |
2944 KB |
Output is correct |
34 |
Correct |
11 ms |
4460 KB |
Output is correct |
35 |
Correct |
2 ms |
2796 KB |
Output is correct |
36 |
Correct |
4 ms |
2944 KB |
Output is correct |
37 |
Correct |
3 ms |
2796 KB |
Output is correct |
38 |
Correct |
4 ms |
2944 KB |
Output is correct |
39 |
Correct |
4 ms |
2796 KB |
Output is correct |
40 |
Correct |
346 ms |
26328 KB |
Output is correct |
41 |
Correct |
405 ms |
25644 KB |
Output is correct |
42 |
Correct |
366 ms |
25620 KB |
Output is correct |
43 |
Correct |
178 ms |
18140 KB |
Output is correct |
44 |
Correct |
193 ms |
18140 KB |
Output is correct |
45 |
Correct |
352 ms |
24840 KB |
Output is correct |
46 |
Correct |
349 ms |
24492 KB |
Output is correct |
47 |
Correct |
376 ms |
26884 KB |
Output is correct |
48 |
Correct |
178 ms |
17500 KB |
Output is correct |
49 |
Correct |
321 ms |
25944 KB |
Output is correct |
50 |
Correct |
340 ms |
25124 KB |
Output is correct |
51 |
Correct |
348 ms |
24808 KB |
Output is correct |