#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <bitset>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <list>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <math.h>
using namespace std;
template <typename input_type>
inline input_type input() {
input_type inp;
cin >> inp;
return inp;
}
const int max_sz = 1e5 + 5;
const long long inf = 1e18;
long long ans[max_sz], dist[3][max_sz];
pair <int, int> sz, pnt, goal;
pair <long long, long long> dp[max_sz];
vector <int> dag, upd[max_sz];
vector <pair <int, int>> graph[max_sz];
void Dijkstra(int root, int idx) {
set <pair <long long, int>> vrtx_lst;
for (int i = 0; i < sz.first; i++) {
dist[idx][i] = (i == root) ? 0 : inf;
vrtx_lst.insert({dist[idx][i], i});
}
while (not vrtx_lst.empty()) {
int vrtx = (*vrtx_lst.begin()).second;
vrtx_lst.erase(vrtx_lst.begin());
for (auto ngh : graph[vrtx]) {
if (dist[idx][ngh.first] > dist[idx][vrtx] + ngh.second) {
vrtx_lst.erase({dist[idx][ngh.first], ngh.first});
dist[idx][ngh.first] = dist[idx][vrtx] + ngh.second, vrtx_lst.insert({dist[idx][ngh.first], ngh.first});
}
}
if (not idx) {
dag.push_back(vrtx);
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
sz = {input<int>(), input<int>()}, pnt = {input<int>() - 1, input<int>() - 1}, goal = {input<int>() - 1, input<int>() - 1};
for (int i = 0; i < sz.second; i++) {
pair <int, int> endpnt = {input<int>() - 1, input<int>() - 1};
int wght = input<int>();
graph[endpnt.first].push_back({endpnt.second, wght}), graph[endpnt.second].push_back({endpnt.first, wght});
}
Dijkstra(pnt.first, 0), Dijkstra(goal.first, 1), Dijkstra(goal.second, 2);
for (int i = 0; i < sz.first; i++) {
for (auto ngh : graph[i]) {
if (dist[0][i] == dist[0][ngh.first] + ngh.second) {
upd[i].push_back(ngh.first);
}
}
}
for (auto vrtx : dag) {
ans[vrtx] = dist[1][vrtx] + dist[2][vrtx], dp[vrtx] = {dist[1][vrtx], dist[2][vrtx]};
for (auto par : upd[vrtx]) {
dp[vrtx] = {min(dp[vrtx].first, dp[par].first), min(dp[vrtx].second, dp[par].second)};
ans[vrtx] = min(ans[vrtx], ans[par]);
}
ans[vrtx] = min(ans[vrtx], min(dist[2][vrtx] + dp[vrtx].first, dist[1][vrtx] + dp[vrtx].second));
}
cout << min(ans[pnt.second], dist[1][goal.second]);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
680 ms |
26268 KB |
Output is correct |
2 |
Correct |
626 ms |
25964 KB |
Output is correct |
3 |
Correct |
624 ms |
26356 KB |
Output is correct |
4 |
Correct |
645 ms |
26328 KB |
Output is correct |
5 |
Correct |
597 ms |
25836 KB |
Output is correct |
6 |
Correct |
718 ms |
26512 KB |
Output is correct |
7 |
Correct |
625 ms |
25964 KB |
Output is correct |
8 |
Correct |
625 ms |
25852 KB |
Output is correct |
9 |
Correct |
657 ms |
26932 KB |
Output is correct |
10 |
Correct |
526 ms |
27048 KB |
Output is correct |
11 |
Correct |
372 ms |
21592 KB |
Output is correct |
12 |
Correct |
656 ms |
26756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
651 ms |
26144 KB |
Output is correct |
2 |
Correct |
679 ms |
26080 KB |
Output is correct |
3 |
Correct |
685 ms |
26044 KB |
Output is correct |
4 |
Correct |
662 ms |
25920 KB |
Output is correct |
5 |
Correct |
649 ms |
25976 KB |
Output is correct |
6 |
Correct |
621 ms |
26260 KB |
Output is correct |
7 |
Correct |
676 ms |
25920 KB |
Output is correct |
8 |
Correct |
775 ms |
25952 KB |
Output is correct |
9 |
Correct |
687 ms |
26044 KB |
Output is correct |
10 |
Correct |
709 ms |
25928 KB |
Output is correct |
11 |
Correct |
392 ms |
21804 KB |
Output is correct |
12 |
Correct |
672 ms |
26252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
6092 KB |
Output is correct |
2 |
Correct |
4 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
20 ms |
7176 KB |
Output is correct |
5 |
Correct |
12 ms |
6016 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
5 ms |
5068 KB |
Output is correct |
8 |
Correct |
6 ms |
5156 KB |
Output is correct |
9 |
Correct |
4 ms |
5160 KB |
Output is correct |
10 |
Correct |
12 ms |
6092 KB |
Output is correct |
11 |
Correct |
3 ms |
5068 KB |
Output is correct |
12 |
Correct |
3 ms |
5068 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
4 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
680 ms |
26268 KB |
Output is correct |
2 |
Correct |
626 ms |
25964 KB |
Output is correct |
3 |
Correct |
624 ms |
26356 KB |
Output is correct |
4 |
Correct |
645 ms |
26328 KB |
Output is correct |
5 |
Correct |
597 ms |
25836 KB |
Output is correct |
6 |
Correct |
718 ms |
26512 KB |
Output is correct |
7 |
Correct |
625 ms |
25964 KB |
Output is correct |
8 |
Correct |
625 ms |
25852 KB |
Output is correct |
9 |
Correct |
657 ms |
26932 KB |
Output is correct |
10 |
Correct |
526 ms |
27048 KB |
Output is correct |
11 |
Correct |
372 ms |
21592 KB |
Output is correct |
12 |
Correct |
656 ms |
26756 KB |
Output is correct |
13 |
Correct |
651 ms |
26144 KB |
Output is correct |
14 |
Correct |
679 ms |
26080 KB |
Output is correct |
15 |
Correct |
685 ms |
26044 KB |
Output is correct |
16 |
Correct |
662 ms |
25920 KB |
Output is correct |
17 |
Correct |
649 ms |
25976 KB |
Output is correct |
18 |
Correct |
621 ms |
26260 KB |
Output is correct |
19 |
Correct |
676 ms |
25920 KB |
Output is correct |
20 |
Correct |
775 ms |
25952 KB |
Output is correct |
21 |
Correct |
687 ms |
26044 KB |
Output is correct |
22 |
Correct |
709 ms |
25928 KB |
Output is correct |
23 |
Correct |
392 ms |
21804 KB |
Output is correct |
24 |
Correct |
672 ms |
26252 KB |
Output is correct |
25 |
Correct |
13 ms |
6092 KB |
Output is correct |
26 |
Correct |
4 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
20 ms |
7176 KB |
Output is correct |
29 |
Correct |
12 ms |
6016 KB |
Output is correct |
30 |
Correct |
4 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
6 ms |
5156 KB |
Output is correct |
33 |
Correct |
4 ms |
5160 KB |
Output is correct |
34 |
Correct |
12 ms |
6092 KB |
Output is correct |
35 |
Correct |
3 ms |
5068 KB |
Output is correct |
36 |
Correct |
3 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
39 |
Correct |
4 ms |
5068 KB |
Output is correct |
40 |
Correct |
731 ms |
26956 KB |
Output is correct |
41 |
Correct |
788 ms |
26684 KB |
Output is correct |
42 |
Correct |
736 ms |
26820 KB |
Output is correct |
43 |
Correct |
391 ms |
21708 KB |
Output is correct |
44 |
Correct |
421 ms |
21700 KB |
Output is correct |
45 |
Correct |
640 ms |
26024 KB |
Output is correct |
46 |
Correct |
570 ms |
25792 KB |
Output is correct |
47 |
Correct |
686 ms |
26312 KB |
Output is correct |
48 |
Correct |
387 ms |
21216 KB |
Output is correct |
49 |
Correct |
643 ms |
26668 KB |
Output is correct |
50 |
Correct |
624 ms |
25888 KB |
Output is correct |
51 |
Correct |
567 ms |
25888 KB |
Output is correct |