Submission #1130040

#TimeUsernameProblemLanguageResultExecution timeMemory
1130040m_bezrutchkaCommuter Pass (JOI18_commuter_pass)C++20
31 / 100
403 ms42456 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> pii; typedef pair<int, pii> pip; typedef pair<pii, int> ppi; typedef pair<pii, pii> ppp; const int LLINF = 2e18 + 10; const int MAXN = 2e5 + 10; int n; vector<pii> adj[MAXN]; vector<int> dijkstra(int s) { vector<int> dist(n + 1, LLINF); vector<int> mrk(n + 1, false); priority_queue<pii> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { int v = pq.top().second; pq.pop(); if (mrk[v]) continue; mrk[v] = true; for (auto [w, c]: adj[v]) { if (!mrk[w] && dist[w] >= dist[v] + c) { dist[w] = dist[v] + c; pq.push({-dist[w], w}); } } } return dist; } int dc[4][MAXN]; bool mrkc[4][MAXN]; priority_queue<pip> pqc; void relax_edge(int tv, int v, int tw, int w, int c) { if (!mrkc[tw][w] && dc[tw][w] > dc[tv][v] + c) { dc[tw][w] = dc[tv][v] + c; pqc.push({-dc[tw][w], {tw, w}}); } } int commuter_pass(int s, int tt) { for (int i = 1; i <= n; i++) { dc[0][i] = dc[1][i] = dc[2][i] = dc[3][i] = LLINF; } dc[0][s] = 0; pqc.push({0, {0, s}}); while (!pqc.empty()) { auto p = pqc.top(); int v = p.second.second, t = p.second.first; pqc.pop(); if (mrkc[t][v]) continue; mrkc[t][v] = true; for (auto [w, c]: adj[v]) { if (c < 0) { if (c == -1 && (t == 0 || t == 1)) { relax_edge(t, v, 1, w, 0); } if (c == -2 && (t == 0 || t == 2)) { relax_edge(t, v, 2, w, 0); } } else { relax_edge(t, v, t, w, c); if (t == 1 || t == 2) { relax_edge(t, v, 3, w, c); } } } } return min({ dc[0][tt], dc[1][tt], dc[2][tt], dc[3][tt] }); } void solve() { int m, house, school, book_u, book_v; cin >> n >> m >> house >> school >> book_u >> book_v; vector<ppi> edges; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); edges.push_back({{a, b}, c}); } vector<int> dh = dijkstra(house); vector<int> ds = dijkstra(school); for (auto &e: edges) { int a = e.first.first, b = e.first.second, c = e.second; if (dh[a] + c + ds[b] == dh[school]) { adj[a].push_back({b, -1}); adj[b].push_back({a, -2}); } if (dh[b] + c + ds[a] == dh[school]) { adj[a].push_back({b, -2}); adj[b].push_back({a, -1}); } } cout << commuter_pass(book_u, book_v) << endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); 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...