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 <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
#define ld long double
using namespace std;
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll,2>>> pq;
vector <array<ll, 2>> adj[100000];
array <ll, 3> rt;
bool visited[100000];
queue <ll> Q;
array <ll, 2> dp[100000];
ll n, m, s, t, x, y, a, b, c, f, dist[3][100000], in[100000];
void dfs(ll u) {
visited[u] = 1;
for (auto [v, x] : adj[u]) {
if (dist[0][v] + x == dist[0][u]) {
++in[v];
if (!visited[v]) dfs(v);
}
}
}
int main() {
cin >> n >> m >> s >> t >> x >> y;
--s, --t, --x, --y;
for (int i=0; i<m; ++i) {
cin >> a >> b >> c;
--a, --b;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
for (int i=0; i<n; ++i) {
for (int j=0; j<3; ++j) {
dist[j][i] = 1e18;
}
}
rt = {s, x, y};
for (int i=0; i<3; ++i) {
dist[i][rt[i]] = 0;
pq.push({0, rt[i]});
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist[i][u] != w) continue;
for (auto [v, x] : adj[u]) {
if (dist[i][v] > w+x) {
dist[i][v] = w+x;
pq.push({dist[i][v], v});
}
}
}
}
dfs(t);
for (int i=0; i<n; ++i) {
dp[i] = {dist[1][i], dist[2][i]};
}
f = dist[1][y];
Q.push(t);
while (!Q.empty()) {
auto u = Q.front();
Q.pop();
f = min(f, dist[1][u] + dp[u][1]);
f = min(f, dist[2][u] + dp[u][0]);
for (auto [v, x] : adj[u]) {
if (dist[0][v] + x == dist[0][u]) {
--in[v];
dp[v][0] = min(dp[v][0], dp[u][0]);
dp[v][1] = min(dp[v][1], dp[u][1]);
if (!in[v]) Q.push(v);
}
}
}
cout << f << '\n';
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:21:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
21 | for (auto [v, x] : adj[u]) {
| ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:48:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | auto [w, u] = pq.top();
| ^
commuter_pass.cpp:51:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for (auto [v, x] : adj[u]) {
| ^
commuter_pass.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for (auto [v, x] : adj[u]) {
| ^
# | 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... |