#include <bits/stdc++.h>
using namespace std;
int N, M, S, T, U, V;
vector<pair<int, int>> graph[100005];
long long dist1[2][100005];
long long dist2[3][100005];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq1;
priority_queue<pair<long long, pair<int, int>>, vector<pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>>> pq2;
void dijkstra1(int n, int t){
pq1.push({0, n});
fill(dist1[t], dist1[t]+1+N, LLONG_MAX/2);
dist1[t][n] = 0;
while(pq1.size()){
auto p = pq1.top();
pq1.pop();
int n = p.second;
if(dist1[t][n] < p.first){
continue;
}
for(auto e : graph[n]){
if(dist1[t][e.first] > dist1[t][n] + e.second){
dist1[t][e.first] = dist1[t][n] + e.second;
pq1.push({dist1[t][e.first], e.first});
}
}
}
}
void dijkstra2(int n){
for(int t = 0; t<3; t++){
fill(dist2[t], dist2[t]+1+N, LLONG_MAX/2);
}
dist2[0][n] = 0;
pq2.push({0, {0, n}});
while(pq2.size()){
auto p = pq2.top();
pq2.pop();
if(dist2[p.second.first][p.second.second] < p.first){
continue;
}
int t = p.second.first, n = p.second.second;
//cout << t << " " << n << " " << dist2[t][n] << endl;
if(t != 2){
if(dist2[t+1][n] > dist2[t][n]){
dist2[t+1][n] = dist2[t][n];
pq2.push({dist2[t+1][n], {t+1, n}});
}
}
for(auto e : graph[n]){
if((t != 1 || dist1[0][n] + e.second + dist1[1][e.first] == dist1[0][T]) && dist2[t][e.first] > dist2[t][n] + e.second){
dist2[t][e.first] = dist2[t][n] + (t == 1 ? 0 : e.second);
pq2.push({dist2[t][e.first], {t, e.first}});
}
}
}
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
cin >> S >> T >> U >> V;
for(int i = 1; i<=M; i++){
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
dijkstra1(S, 0);
dijkstra1(T, 1);
dijkstra2(U);
long long ans = dist2[2][V];
dijkstra2(V);
ans = min(dist2[2][U], ans);
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
441 ms |
22240 KB |
Output is correct |
2 |
Correct |
461 ms |
19560 KB |
Output is correct |
3 |
Correct |
451 ms |
21860 KB |
Output is correct |
4 |
Correct |
443 ms |
21988 KB |
Output is correct |
5 |
Correct |
428 ms |
19180 KB |
Output is correct |
6 |
Correct |
446 ms |
22116 KB |
Output is correct |
7 |
Correct |
451 ms |
19436 KB |
Output is correct |
8 |
Correct |
443 ms |
19440 KB |
Output is correct |
9 |
Correct |
450 ms |
20200 KB |
Output is correct |
10 |
Correct |
384 ms |
20080 KB |
Output is correct |
11 |
Correct |
196 ms |
13028 KB |
Output is correct |
12 |
Correct |
465 ms |
20076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
489 ms |
19692 KB |
Output is correct |
2 |
Correct |
490 ms |
19432 KB |
Output is correct |
3 |
Correct |
458 ms |
19436 KB |
Output is correct |
4 |
Correct |
477 ms |
19436 KB |
Output is correct |
5 |
Correct |
463 ms |
19564 KB |
Output is correct |
6 |
Correct |
449 ms |
21860 KB |
Output is correct |
7 |
Correct |
458 ms |
19308 KB |
Output is correct |
8 |
Correct |
474 ms |
19432 KB |
Output is correct |
9 |
Correct |
460 ms |
19432 KB |
Output is correct |
10 |
Correct |
487 ms |
19560 KB |
Output is correct |
11 |
Correct |
194 ms |
12912 KB |
Output is correct |
12 |
Correct |
456 ms |
21904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
3840 KB |
Output is correct |
2 |
Correct |
6 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
23 ms |
4864 KB |
Output is correct |
5 |
Correct |
15 ms |
3840 KB |
Output is correct |
6 |
Correct |
7 ms |
2816 KB |
Output is correct |
7 |
Correct |
7 ms |
2816 KB |
Output is correct |
8 |
Correct |
8 ms |
2944 KB |
Output is correct |
9 |
Correct |
7 ms |
2816 KB |
Output is correct |
10 |
Correct |
14 ms |
3840 KB |
Output is correct |
11 |
Correct |
6 ms |
2688 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
6 ms |
2816 KB |
Output is correct |
14 |
Correct |
7 ms |
2816 KB |
Output is correct |
15 |
Correct |
7 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
441 ms |
22240 KB |
Output is correct |
2 |
Correct |
461 ms |
19560 KB |
Output is correct |
3 |
Correct |
451 ms |
21860 KB |
Output is correct |
4 |
Correct |
443 ms |
21988 KB |
Output is correct |
5 |
Correct |
428 ms |
19180 KB |
Output is correct |
6 |
Correct |
446 ms |
22116 KB |
Output is correct |
7 |
Correct |
451 ms |
19436 KB |
Output is correct |
8 |
Correct |
443 ms |
19440 KB |
Output is correct |
9 |
Correct |
450 ms |
20200 KB |
Output is correct |
10 |
Correct |
384 ms |
20080 KB |
Output is correct |
11 |
Correct |
196 ms |
13028 KB |
Output is correct |
12 |
Correct |
465 ms |
20076 KB |
Output is correct |
13 |
Correct |
489 ms |
19692 KB |
Output is correct |
14 |
Correct |
490 ms |
19432 KB |
Output is correct |
15 |
Correct |
458 ms |
19436 KB |
Output is correct |
16 |
Correct |
477 ms |
19436 KB |
Output is correct |
17 |
Correct |
463 ms |
19564 KB |
Output is correct |
18 |
Correct |
449 ms |
21860 KB |
Output is correct |
19 |
Correct |
458 ms |
19308 KB |
Output is correct |
20 |
Correct |
474 ms |
19432 KB |
Output is correct |
21 |
Correct |
460 ms |
19432 KB |
Output is correct |
22 |
Correct |
487 ms |
19560 KB |
Output is correct |
23 |
Correct |
194 ms |
12912 KB |
Output is correct |
24 |
Correct |
456 ms |
21904 KB |
Output is correct |
25 |
Correct |
15 ms |
3840 KB |
Output is correct |
26 |
Correct |
6 ms |
2816 KB |
Output is correct |
27 |
Correct |
6 ms |
2816 KB |
Output is correct |
28 |
Correct |
23 ms |
4864 KB |
Output is correct |
29 |
Correct |
15 ms |
3840 KB |
Output is correct |
30 |
Correct |
7 ms |
2816 KB |
Output is correct |
31 |
Correct |
7 ms |
2816 KB |
Output is correct |
32 |
Correct |
8 ms |
2944 KB |
Output is correct |
33 |
Correct |
7 ms |
2816 KB |
Output is correct |
34 |
Correct |
14 ms |
3840 KB |
Output is correct |
35 |
Correct |
6 ms |
2688 KB |
Output is correct |
36 |
Correct |
6 ms |
2688 KB |
Output is correct |
37 |
Correct |
6 ms |
2816 KB |
Output is correct |
38 |
Correct |
7 ms |
2816 KB |
Output is correct |
39 |
Correct |
7 ms |
2816 KB |
Output is correct |
40 |
Correct |
445 ms |
22500 KB |
Output is correct |
41 |
Correct |
463 ms |
20080 KB |
Output is correct |
42 |
Correct |
450 ms |
20204 KB |
Output is correct |
43 |
Correct |
230 ms |
13040 KB |
Output is correct |
44 |
Correct |
238 ms |
13040 KB |
Output is correct |
45 |
Correct |
437 ms |
19052 KB |
Output is correct |
46 |
Correct |
430 ms |
18672 KB |
Output is correct |
47 |
Correct |
465 ms |
21988 KB |
Output is correct |
48 |
Correct |
249 ms |
12528 KB |
Output is correct |
49 |
Correct |
408 ms |
22116 KB |
Output is correct |
50 |
Correct |
443 ms |
18408 KB |
Output is correct |
51 |
Correct |
409 ms |
18928 KB |
Output is correct |