Submission #654304

#TimeUsernameProblemLanguageResultExecution timeMemory
654304lunchbox1Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
534 ms22648 KiB
/* Commuter Pass https://oj.uz/problem/view/JOI18_commuter_pass */ #include <bits/stdc++.h> using namespace std; typedef long long LL; template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>; const int N = 1e5; const LL INF = 1e18; int main() { ios::sync_with_stdio(0), cin.tie(0); int n, m; cin >> n >> m; int s, t, u, v; cin >> s >> t >> u >> v, s--, t--, u--, v--; static vector<pair<int, int>> g[N]; while (m--) { int i, j, c; cin >> i >> j >> c, i--, j--; g[i].push_back({j, c}), g[j].push_back({i, c}); } auto gen = [&](int s, LL *dt) { min_pq<pair<LL, int>> q; fill(dt, dt + n, INF); q.push({dt[s] = 0, s}); while (!q.empty()) { auto [d, i] = q.top(); q.pop(); if (d != dt[i]) continue; for (auto [j, c] : g[i]) if (d + c < dt[j]) q.push({dt[j] = d + c, j}); } }; static LL ds[N], dt[N]; gen(s, ds), gen(t, dt); static LL f[N][3]; LL all = ds[t]; for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF; min_pq<tuple<LL, int, int>> q; q.push({f[u][0] = 0, u, 0}); while (!q.empty()) { auto [d, i, t] = q.top(); q.pop(); if (d != f[i][t]) continue; for (auto [j, c] : g[i]) { if ((t == 0 || t == 1) && ds[i] + dt[j] + c == all && d < f[j][1]) q.push({f[j][1] = d, j, 1}); if (t == 0 && d + c < f[j][0]) q.push({f[j][0] = d + c, j, 0}); if ((t == 1 || t == 2) && d + c < f[j][2]) q.push({f[j][2] = d + c, j, 2}); } } LL tmp = min({f[v][0], f[v][1], f[v][2]}); for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF; q.push({f[u][0] = 0, u, 0}); while (!q.empty()) { auto [d, i, t] = q.top(); q.pop(); if (d != f[i][t]) continue; for (auto [j, c] : g[i]) { if ((t == 0 || t == 1) && dt[i] + ds[j] + c == all && d < f[j][1]) q.push({f[j][1] = d, j, 1}); if (t == 0 && d + c < f[j][0]) q.push({f[j][0] = d + c, j, 0}); if ((t == 1 || t == 2) && d + c < f[j][2]) q.push({f[j][2] = d + c, j, 2}); } } tmp = min(tmp, min({f[v][0], f[v][1], f[v][2]})); cout << tmp << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...