제출 #683556

#제출 시각아이디문제언어결과실행 시간메모리
68355642kangarooCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
648 ms67976 KiB
// // Created by 42kangaroo on 17/01/2023. // #include <bits/stdc++.h> using namespace std; #define int long long struct Edge { int fr, to, w; }; struct nEdge { int to, w; int stat; }; bool operator>(const Edge &l, const Edge &r) { return l.w > r.w; } bool operator>(const nEdge &l, const nEdge &r) { return l.w > r.w; } using g_t = vector<vector<Edge>>; void dfs(int n, g_t &gr, g_t &outB, g_t &outF, vector<bool>& vis) { if (vis[n])return; vis[n] = true; for (auto e: gr[n]) { outB[n].push_back(e); outF[e.to].push_back({e.to, e.fr, 0}); dfs(e.to, gr, outB, outF, vis); } } g_t dijkstra(g_t &gr, int s, int t) { vector<int> dist(gr.size(), -1); priority_queue<Edge, vector<Edge>, greater<>> q; q.push({s, s, 0}); g_t back(gr.size()); while (!q.empty()) { auto ed = q.top(); q.pop(); if (dist[ed.to] != -1 && dist[ed.to] < ed.w) continue; back[ed.to].push_back({ed.to, ed.fr, 0}); if (dist[ed.to] == -1) { dist[ed.to] = ed.w; for (auto &e: gr[ed.to]) { auto ne = e; ne.w = ed.w + e.w; q.push(ne); } } } return back; } int dijkstradist(g_t &gr, g_t &ba, g_t &fr, int u, int v) { array<vector<int>, 4> d{}; d.fill(vector<int>(gr.size(), -1)); priority_queue<nEdge, vector<nEdge>, greater<>> q; q.push({u, 0, 0}); while (!q.empty()) { auto ed = q.top(); q.pop(); if (ed.to == v) { return ed.w; } if (d[ed.stat][ed.to] != -1) continue; d[ed.stat][ed.to] = ed.w; for (auto e: gr[ed.to]) { if (ed.stat == 0) { q.push({e.to, e.w + ed.w, 0}); } else { q.push({e.to, e.w + ed.w, 3}); } } if (ed.stat < 2) { for (auto e: fr[ed.to]) { q.push({e.to, e.w + ed.w, 1}); } } if (!(ed.stat & 1)) { for (auto e: ba[ed.to]) { q.push({e.to, e.w + ed.w, 2}); } } } return -1; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; --s; --t; --u; --v; g_t gr(n); for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; --a; --b; gr[a].push_back({a, b, c}); gr[b].push_back({b, a, c}); } auto back = dijkstra(gr, s, t); g_t backR(n), frontR(n); vector<bool> vis(n, false); dfs(t, back, backR, frontR, vis); cout << dijkstradist(gr, backR, frontR, u, v) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...