#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;
// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
//***************** CONSTANTS *****************
const int MXN = 100001;
const int64_t INF = 1'000'000'000'000'000'000;
//***************** GLOBAL VARIABLES *****************
vector<array<int64_t, 2>> g[MXN];
int64_t d[3][MXN], ans;
//***************** AUXILIARY STRUCTS *****************
void dijkstra(int node, int64_t dist[]){
priority_queue< pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>> > pq;
fill(dist, dist + MXN, INF);
pq.emplace(0, node);
dist[node] = 0;
while(!pq.empty()){
auto [dir, u] = pq.top();
pq.pop();
if(dir > dist[u])
continue;
for(const auto& [v, w] : g[u]){
if(dist[v] > dist[u] + w){
pq.emplace(dist[u] + w, v);
dist[v] = dist[u] + w;
}
}
}
}
void parent(int start, int end, int64_t dist[]){
priority_queue< array<int64_t, 3>, vector<array<int64_t, 3>>, greater<array<int64_t, 3>> > pq;
int64_t dp[2][MXN];
bool vis[MXN];
fill(dp[0], dp[0] + MXN, INF);
fill(dp[1], dp[1] + MXN, INF);
fill(dist, dist + MXN, INF);
memset(vis, 0, sizeof vis);
pq.push({0, start, 0});
dist[start] = 0;
while(!pq.empty()){
auto [dir, u, par] = pq.top();
pq.pop();
if(!vis[u]){
vis[u] = 1;
dist[u] = dir;
for(const auto& [v, w] : g[u]){
pq.push({dir + w, v, u});
}
dp[0][u] = min(d[0][u], dp[0][par]);
dp[1][u] = min(d[1][u], dp[1][par]);
}
else if(dist[u] == dir){
if(min(d[0][u], dp[0][par]) + min(d[1][u], dp[1][par]) <= dp[0][u] + dp[1][u]){
dp[0][u] = min(d[0][u], dp[0][par]);
dp[1][u] = min(d[1][u], dp[1][par]);
}
}
}
ans = min(ans, dp[0][end] + dp[1][end]);
}
//***************** MAIN BODY *****************
void solve(){
int N, M, S, T, U, V;
cin >> N >> M >> S >> T >> U >> V;
for(int i = 0; i < M; i++){
int u, v;
int64_t w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dijkstra(U, d[0]);
dijkstra(V, d[1]);
ans = d[0][V];
parent(S, T, d[2]);
parent(T, S, d[2]);
cout << ans << '\n';
}
//***************** *****************
int32_t main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
#ifdef LOCAL
auto begin = high_resolution_clock::now();
#endif
int tc = 1;
// cin >> tc;
for (int t = 0; t < tc; t++)
solve();
#ifdef LOCAL
auto end = high_resolution_clock::now();
cout << fixed << setprecision(4);
cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
#endif
return 0;
}
/*
If code gives a WA, check for the following :
1. I/O format
2. Are you clearing all global variables in between tests if multitests are a thing
3. Can you definitively prove the logic
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
518 ms |
27296 KB |
Output is correct |
2 |
Correct |
494 ms |
26668 KB |
Output is correct |
3 |
Correct |
491 ms |
26272 KB |
Output is correct |
4 |
Correct |
519 ms |
26232 KB |
Output is correct |
5 |
Correct |
443 ms |
23108 KB |
Output is correct |
6 |
Correct |
581 ms |
27084 KB |
Output is correct |
7 |
Correct |
459 ms |
26536 KB |
Output is correct |
8 |
Correct |
483 ms |
30168 KB |
Output is correct |
9 |
Correct |
506 ms |
31484 KB |
Output is correct |
10 |
Correct |
484 ms |
31212 KB |
Output is correct |
11 |
Correct |
140 ms |
13892 KB |
Output is correct |
12 |
Correct |
549 ms |
31480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
512 ms |
26848 KB |
Output is correct |
2 |
Correct |
474 ms |
23000 KB |
Output is correct |
3 |
Correct |
469 ms |
26292 KB |
Output is correct |
4 |
Correct |
465 ms |
23100 KB |
Output is correct |
5 |
Correct |
460 ms |
22876 KB |
Output is correct |
6 |
Correct |
497 ms |
26232 KB |
Output is correct |
7 |
Correct |
456 ms |
22960 KB |
Output is correct |
8 |
Correct |
486 ms |
23096 KB |
Output is correct |
9 |
Correct |
474 ms |
22884 KB |
Output is correct |
10 |
Correct |
499 ms |
26288 KB |
Output is correct |
11 |
Correct |
178 ms |
11904 KB |
Output is correct |
12 |
Correct |
486 ms |
26168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
9256 KB |
Output is correct |
2 |
Correct |
4 ms |
6724 KB |
Output is correct |
3 |
Correct |
4 ms |
6732 KB |
Output is correct |
4 |
Correct |
59 ms |
12492 KB |
Output is correct |
5 |
Correct |
32 ms |
10712 KB |
Output is correct |
6 |
Correct |
7 ms |
6780 KB |
Output is correct |
7 |
Correct |
7 ms |
6988 KB |
Output is correct |
8 |
Correct |
8 ms |
7056 KB |
Output is correct |
9 |
Correct |
5 ms |
6860 KB |
Output is correct |
10 |
Correct |
31 ms |
10672 KB |
Output is correct |
11 |
Correct |
4 ms |
6604 KB |
Output is correct |
12 |
Correct |
4 ms |
6684 KB |
Output is correct |
13 |
Correct |
4 ms |
6640 KB |
Output is correct |
14 |
Correct |
5 ms |
6732 KB |
Output is correct |
15 |
Correct |
5 ms |
6736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
518 ms |
27296 KB |
Output is correct |
2 |
Correct |
494 ms |
26668 KB |
Output is correct |
3 |
Correct |
491 ms |
26272 KB |
Output is correct |
4 |
Correct |
519 ms |
26232 KB |
Output is correct |
5 |
Correct |
443 ms |
23108 KB |
Output is correct |
6 |
Correct |
581 ms |
27084 KB |
Output is correct |
7 |
Correct |
459 ms |
26536 KB |
Output is correct |
8 |
Correct |
483 ms |
30168 KB |
Output is correct |
9 |
Correct |
506 ms |
31484 KB |
Output is correct |
10 |
Correct |
484 ms |
31212 KB |
Output is correct |
11 |
Correct |
140 ms |
13892 KB |
Output is correct |
12 |
Correct |
549 ms |
31480 KB |
Output is correct |
13 |
Correct |
512 ms |
26848 KB |
Output is correct |
14 |
Correct |
474 ms |
23000 KB |
Output is correct |
15 |
Correct |
469 ms |
26292 KB |
Output is correct |
16 |
Correct |
465 ms |
23100 KB |
Output is correct |
17 |
Correct |
460 ms |
22876 KB |
Output is correct |
18 |
Correct |
497 ms |
26232 KB |
Output is correct |
19 |
Correct |
456 ms |
22960 KB |
Output is correct |
20 |
Correct |
486 ms |
23096 KB |
Output is correct |
21 |
Correct |
474 ms |
22884 KB |
Output is correct |
22 |
Correct |
499 ms |
26288 KB |
Output is correct |
23 |
Correct |
178 ms |
11904 KB |
Output is correct |
24 |
Correct |
486 ms |
26168 KB |
Output is correct |
25 |
Correct |
33 ms |
9256 KB |
Output is correct |
26 |
Correct |
4 ms |
6724 KB |
Output is correct |
27 |
Correct |
4 ms |
6732 KB |
Output is correct |
28 |
Correct |
59 ms |
12492 KB |
Output is correct |
29 |
Correct |
32 ms |
10712 KB |
Output is correct |
30 |
Correct |
7 ms |
6780 KB |
Output is correct |
31 |
Correct |
7 ms |
6988 KB |
Output is correct |
32 |
Correct |
8 ms |
7056 KB |
Output is correct |
33 |
Correct |
5 ms |
6860 KB |
Output is correct |
34 |
Correct |
31 ms |
10672 KB |
Output is correct |
35 |
Correct |
4 ms |
6604 KB |
Output is correct |
36 |
Correct |
4 ms |
6684 KB |
Output is correct |
37 |
Correct |
4 ms |
6640 KB |
Output is correct |
38 |
Correct |
5 ms |
6732 KB |
Output is correct |
39 |
Correct |
5 ms |
6736 KB |
Output is correct |
40 |
Correct |
508 ms |
30808 KB |
Output is correct |
41 |
Correct |
538 ms |
31384 KB |
Output is correct |
42 |
Correct |
530 ms |
31300 KB |
Output is correct |
43 |
Correct |
167 ms |
14024 KB |
Output is correct |
44 |
Correct |
148 ms |
14012 KB |
Output is correct |
45 |
Correct |
500 ms |
25080 KB |
Output is correct |
46 |
Correct |
457 ms |
24820 KB |
Output is correct |
47 |
Correct |
554 ms |
26608 KB |
Output is correct |
48 |
Correct |
180 ms |
13444 KB |
Output is correct |
49 |
Correct |
458 ms |
29448 KB |
Output is correct |
50 |
Correct |
438 ms |
25152 KB |
Output is correct |
51 |
Correct |
490 ms |
25100 KB |
Output is correct |