| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 989335 | eysbutno | Commuter Pass (JOI18_commuter_pass) | C++11 | 0 ms | 0 KiB |
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>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
template<class T> bool smax(T &a, T b) {
return a < b ? a = b, 1 : 0;
}
template<class T> bool smin(T &a, T b) {
return a > b ? a = b, 1 : 0;
}
constexpr ll INF = 1e18;
void solve() {
int n, m;
cin >> n >> m;
pii a, b;
cin >> a[0] >> a[1] >> b[0] >> b[1];
--a[0], --a[1], --b[0], --b[1];
vector<vector<pii>> adj(n);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[--u].push_back({--v, w});
adj[v].push_back({u, w});
}
using pll = array<ll, 2>;
vector<vector<int>> alt(n);
priority_queue<pll, vector<pll>, greater<>> pq;
{
vector<ll> tdist(n, INF);
pq.push({tdist[a[0]] = 0, a[0]});
while (!pq.empty()) {
auto [t, u] = pq.top(); pq.pop();
if (tdist[u] != t) continue;
for (auto [v, w] : adj[u]) {
if (smin(tdist[v], t + w)) {
alt[v] = {(int) u};
pq.push({tdist[v], v});
} else if (tdist[v] == t + w) {
alt[v].push_back((int) u);
}
}
}
}
vector dist(2, vector(n, INF));
for (int id = 0; id < 2; id++) {
pq.push({dist[id][b[id]] = 0, b[id]});
while (!pq.empty()) {
auto [t, u] = pq.top(); pq.pop();
if (t != dist[id][u]) continue;
for (auto [v, w] : adj[u]) {
if (smin(dist[id][v], t + w)) {
pq.push({t + w, v});
}
}
}
}
ll res = dist[0][b[1]];
vector<pll> dp(n, {INF, INF});
int cnt = 0;
auto dfs = [&](int u, auto &&self) -> void {
dp[u] = {dist[0][u], dist[1][u]};
for (int v : alt[u]) {
self(v, self);
for (int id = 0; id < 2; id++) {
smin(dp[u][id], dp[v][id]);
}
}
for (int id = 0; id < 2; id++) {
smin(res, dist[id][u] + dp[u][!id]);
}
++cnt; if (cnt > (int) 1e6) assert(false);
};
dfs(a[1], dfs);
cout << res << "\n";
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1; // cin >> t;
while (t--) solve();
}
/**
* Construct an alternate graph with all the
* edges in possible shortest paths from S to T.
* Any path from U to V can take any "vertical" path
* on this alternate graph (b/c it's a DAG). So,
* consider this alternate graph and DP on the DAG.
*/