Submission #755199

#TimeUsernameProblemLanguageResultExecution timeMemory
755199siewjhCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
384 ms36428 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; const ll inf = 1e18; int nodes, edges; vector<pair<int, ll>> adj[MAXN]; void dijkstra(int source, vector<ll> &dist){ priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, source}); for (int i = 1; i <= nodes; i++) dist[i] = inf; dist[source] = 0; while (!pq.empty()){ ll d = pq.top().first; int x = pq.top().second; pq.pop(); if (dist[x] != d) continue; for (auto nxt : adj[x]){ int nn = nxt.first; ll nd = nxt.second; if (d + nd < dist[nn]){ dist[nn] = d + nd; pq.push({dist[nn], nn}); } } } } ll dp(int x, vector<vector<int>> &spadj, vector<ll> &ddest, vector<ll> &memo){ if (memo[x] != -1) return memo[x]; ll ans = ddest[x]; for (int nxt : spadj[x]) ans = min(ans, dp(nxt, spadj, ddest, memo)); return memo[x] = ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int s, t, u, v; cin >> nodes >> edges >> s >> t >> u >> v; vector<tuple<int, int, ll>> elist(edges); for (int i = 0; i < edges; i++){ int a, b; ll d; cin >> a >> b >> d; adj[a].push_back({b, d}); adj[b].push_back({a, d}); elist[i] = {a, b, d}; } vector<ll> ds(nodes + 1), dt(nodes + 1), du(nodes + 1), dv(nodes + 1); dijkstra(s, ds); dijkstra(t, dt); dijkstra(u, du); dijkstra(v, dv); ll dst = ds[t]; vector<vector<int>> stot(nodes + 1), ttos(nodes + 1); for (auto edge : elist){ int a, b; ll d; tie(a, b, d) = edge; if (ds[a] + d + dt[b] == dst){ stot[a].push_back(b); ttos[b].push_back(a); } else if (ds[b] + d + dt[a] == dst){ stot[b].push_back(a); ttos[a].push_back(b); } } vector<ll> memo1(nodes + 1, -1), memo2(nodes + 1, -1); ll ans = du[v]; for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, stot, dv, memo1)); for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, ttos, dv, memo2)); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...