This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 1e5 + 1;
int n, m, S, T, U, V;
ll dist[2][maxn], dist2[4][maxn];
vector <pair <int, ll>> adj[maxn];
set <pair <ll, int>> s;
set <vector <ll>> s2;
void dijkstra (int src, int x){
fill(dist[x], dist[x] + n + 1, 1e15);
dist[x][src] = 0;
s.insert({dist[x][src], src});
for (int i = 0; i < n; i++){
int v = (*s.begin()).second;
s.erase(s.begin());
for (auto [u, w] : adj[v]){
if (dist[x][u] <= dist[x][v] + w)
continue;
s.erase({dist[x][u], u});
dist[x][u] = dist[x][v] + w;
s.insert({dist[x][u], u});
}
if (!s.size())
break;
}
}
void dijkstra2 (){
for (int i = 0; i < 4; i++)
fill(dist2[i], dist2[i] + n + 1, 1e15);
dist2[0][U] = 0;
s2.insert({0, U, 0, -1});
while (s2.size()){
vector <ll> x = (*s2.begin());
ll c = x[0], v = x[1], st = x[2], par = x[3];
s2.erase(s2.begin());
if (st == 0){
for (auto [u, w] : adj[v]){
// check whether we go through the shortest subpath in the opposing direction as s does or not
if (dist[0][v] + dist[1][u] + w == dist[0][T]){
if (dist2[1][u] <= dist2[st][v])
continue;
dist2[1][u] = dist2[st][v];
s2.insert({dist2[1][u], u, 1, v});
}
if (dist[1][v] + dist[0][u] + w == dist[0][T]){
if (dist2[2][u] <= dist2[st][v])
continue;
dist2[2][u] = dist2[st][v];
s2.insert({dist2[2][u], u, 2, v});
}
}
for (auto [u, w] : adj[v]){
// we choose not to enter through the shortest path node or the node is not a part of a shortest path
if (dist2[0][u] <= dist2[st][v] + w)
continue;
dist2[0][u] = dist2[st][v] + w;
s2.insert({dist2[0][u], u, 0, v});
}
}
if (st == 1){
// state where we go in the same flow as s to t (s -> t)
for (auto [u, w] : adj[v]){
if (dist[0][v] + dist[1][u] + w == dist[0][T]){
if (dist2[1][u] <= dist2[st][v])
continue;
dist2[1][u] = dist2[st][v];
s2.insert({dist2[1][u], u, 1, v});
}
else{
if (dist2[3][u] <= dist2[st][v] + w)
continue;
dist2[3][u] = dist2[st][v] + w;
s2.insert({dist2[3][u], u, 3, v});
}
}
}
if (st == 2){
// state where we go in the opposing flow (t -> s)
for (auto [u, w] : adj[v]){
if (dist[1][v] + dist[0][u] + w == dist[0][T]){
if (dist2[2][u] <= dist2[st][v])
continue;
dist2[2][u] = dist2[st][v] + w;
s2.insert({dist2[2][u], u, 2, v});
}
else{
if (dist2[3][u] <= dist2[st][v] + w)
continue;
dist2[3][u] = dist2[st][v] + w;
s2.insert({dist2[3][u], u, 3, v});
}
}
}
if (st == 3){
// state where we have finished making use of s -> t
for (auto [u, w] : adj[v]){
if (dist2[3][u] <= dist2[st][v] + w)
continue;
dist2[3][u] = dist2[st][v] + w;
s2.insert({dist2[3][u], u, 3, v});
}
}
}
}
int main (){
ios_base::sync_with_stdio(0);
cin >> n >> m >> S >> T >> U >> V;
for (int x, y, z, i = 0; i < m; i++){
cin >> x >> y >> z;
adj[x].pb({y, z});
adj[y].pb({x, z});
}
dijkstra(S, 0);
dijkstra(T, 1);
dijkstra2();
cout << min({dist2[0][V], dist2[1][V], dist2[2][V], dist2[3][V]});
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void dijkstra2()':
commuter_pass.cpp:42:6: warning: unused variable 'c' [-Wunused-variable]
42 | ll c = x[0], v = x[1], st = x[2], par = x[3];
| ^
commuter_pass.cpp:42:37: warning: unused variable 'par' [-Wunused-variable]
42 | ll c = x[0], v = x[1], st = x[2], par = x[3];
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |