#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
vector<array<int, 2>> adj[N], dag[N];
int n;
void dijkstra(int s, long long *dist) {
priority_queue<array<long long, 2>> queue;
fill(dist, dist + n + 1, LLONG_MAX);
queue.push({0, s});
dist[s] = 0;
while (!queue.empty()) {
auto [d, u] = queue.top();
queue.pop();
d = -d;
if (d > dist[u]) {
continue;
}
for (auto [c, w] : adj[u]) {
if (d + w < dist[c]) {
dist[c] = d + w;
queue.push({-dist[c], c});
}
}
}
}
long long dist[3][N];
long long solve(int s, int t) {
priority_queue<array<long long, 3>> queue;
for (int i = 0; i < 3; ++i) {
fill(dist[i], dist[i] + n + 1, LLONG_MAX);
}
queue.push({0, s, 0});
dist[0][s] = 0;
while (!queue.empty()) {
auto [d, u, k] = queue.top();
queue.pop();
d = -d;
if (d > dist[k][u]) {
continue;
}
if (k < 2 && d < dist[k + 1][u]) {
dist[k + 1][u] = d;
queue.push(array<long long, 3>{-d, u, k + 1});
}
for (auto [c, w] : (k == 1 ? dag[u] : adj[u])) {
if (d + w < dist[k][c]) {
dist[k][c] = d + w;
queue.push(array<long long, 3>{-dist[k][c], c, k});
}
}
}
return dist[2][t];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, s, t, x, y;
cin >> n >> m >> s >> t >> x >> y;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dijkstra(s, dist[0]);
dijkstra(t, dist[1]);
for (int i = 1; i <= n; ++i) {
for (auto [j, w] : adj[i]) {
if (dist[0][i] + w + dist[1][j] == dist[0][t]) {
dag[i].push_back({j, 0});
}
}
}
cout << min(solve(x, y), solve(y, x)) << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
515 ms |
23172 KB |
Output is correct |
2 |
Correct |
537 ms |
22796 KB |
Output is correct |
3 |
Correct |
559 ms |
28072 KB |
Output is correct |
4 |
Correct |
564 ms |
25132 KB |
Output is correct |
5 |
Correct |
549 ms |
23300 KB |
Output is correct |
6 |
Correct |
513 ms |
27140 KB |
Output is correct |
7 |
Correct |
530 ms |
23792 KB |
Output is correct |
8 |
Correct |
550 ms |
23628 KB |
Output is correct |
9 |
Correct |
496 ms |
22952 KB |
Output is correct |
10 |
Correct |
422 ms |
23052 KB |
Output is correct |
11 |
Correct |
224 ms |
15040 KB |
Output is correct |
12 |
Correct |
532 ms |
22992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
545 ms |
20144 KB |
Output is correct |
2 |
Correct |
539 ms |
23272 KB |
Output is correct |
3 |
Correct |
536 ms |
23028 KB |
Output is correct |
4 |
Correct |
585 ms |
23212 KB |
Output is correct |
5 |
Correct |
553 ms |
23412 KB |
Output is correct |
6 |
Correct |
532 ms |
26520 KB |
Output is correct |
7 |
Correct |
549 ms |
24256 KB |
Output is correct |
8 |
Correct |
547 ms |
23240 KB |
Output is correct |
9 |
Correct |
566 ms |
23476 KB |
Output is correct |
10 |
Correct |
581 ms |
23100 KB |
Output is correct |
11 |
Correct |
267 ms |
16188 KB |
Output is correct |
12 |
Correct |
566 ms |
26556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
5836 KB |
Output is correct |
2 |
Correct |
4 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5028 KB |
Output is correct |
4 |
Correct |
19 ms |
7116 KB |
Output is correct |
5 |
Correct |
12 ms |
6080 KB |
Output is correct |
6 |
Correct |
5 ms |
5068 KB |
Output is correct |
7 |
Correct |
5 ms |
5196 KB |
Output is correct |
8 |
Correct |
6 ms |
5196 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
11 ms |
6124 KB |
Output is correct |
11 |
Correct |
3 ms |
5068 KB |
Output is correct |
12 |
Correct |
4 ms |
5068 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
5 ms |
5068 KB |
Output is correct |
15 |
Correct |
5 ms |
5032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
515 ms |
23172 KB |
Output is correct |
2 |
Correct |
537 ms |
22796 KB |
Output is correct |
3 |
Correct |
559 ms |
28072 KB |
Output is correct |
4 |
Correct |
564 ms |
25132 KB |
Output is correct |
5 |
Correct |
549 ms |
23300 KB |
Output is correct |
6 |
Correct |
513 ms |
27140 KB |
Output is correct |
7 |
Correct |
530 ms |
23792 KB |
Output is correct |
8 |
Correct |
550 ms |
23628 KB |
Output is correct |
9 |
Correct |
496 ms |
22952 KB |
Output is correct |
10 |
Correct |
422 ms |
23052 KB |
Output is correct |
11 |
Correct |
224 ms |
15040 KB |
Output is correct |
12 |
Correct |
532 ms |
22992 KB |
Output is correct |
13 |
Correct |
545 ms |
20144 KB |
Output is correct |
14 |
Correct |
539 ms |
23272 KB |
Output is correct |
15 |
Correct |
536 ms |
23028 KB |
Output is correct |
16 |
Correct |
585 ms |
23212 KB |
Output is correct |
17 |
Correct |
553 ms |
23412 KB |
Output is correct |
18 |
Correct |
532 ms |
26520 KB |
Output is correct |
19 |
Correct |
549 ms |
24256 KB |
Output is correct |
20 |
Correct |
547 ms |
23240 KB |
Output is correct |
21 |
Correct |
566 ms |
23476 KB |
Output is correct |
22 |
Correct |
581 ms |
23100 KB |
Output is correct |
23 |
Correct |
267 ms |
16188 KB |
Output is correct |
24 |
Correct |
566 ms |
26556 KB |
Output is correct |
25 |
Correct |
12 ms |
5836 KB |
Output is correct |
26 |
Correct |
4 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5028 KB |
Output is correct |
28 |
Correct |
19 ms |
7116 KB |
Output is correct |
29 |
Correct |
12 ms |
6080 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5196 KB |
Output is correct |
32 |
Correct |
6 ms |
5196 KB |
Output is correct |
33 |
Correct |
4 ms |
5068 KB |
Output is correct |
34 |
Correct |
11 ms |
6124 KB |
Output is correct |
35 |
Correct |
3 ms |
5068 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
5 ms |
5068 KB |
Output is correct |
39 |
Correct |
5 ms |
5032 KB |
Output is correct |
40 |
Correct |
502 ms |
28372 KB |
Output is correct |
41 |
Correct |
507 ms |
23716 KB |
Output is correct |
42 |
Correct |
529 ms |
23492 KB |
Output is correct |
43 |
Correct |
305 ms |
17012 KB |
Output is correct |
44 |
Correct |
323 ms |
16608 KB |
Output is correct |
45 |
Correct |
551 ms |
24980 KB |
Output is correct |
46 |
Correct |
540 ms |
24764 KB |
Output is correct |
47 |
Correct |
566 ms |
26544 KB |
Output is correct |
48 |
Correct |
290 ms |
16108 KB |
Output is correct |
49 |
Correct |
419 ms |
27956 KB |
Output is correct |
50 |
Correct |
585 ms |
25012 KB |
Output is correct |
51 |
Correct |
594 ms |
26312 KB |
Output is correct |