제출 #1036843

#제출 시각아이디문제언어결과실행 시간메모리
1036843juicyOlympic Bus (JOI20_ho_t4)C++17
0 / 100
95 ms3932 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 205, M = 5e4 + 5; const int inf = 1e9; int n, m; int pr[N], w[M], d[2][N]; array<int, 2> f[N]; bool spec[M]; vector<array<int, 2>> g[N], rg[N]; array<int, 3> edges[M]; void dijkstra(int s, int *d) { using T = array<int, 2>; priority_queue<T, vector<T>, greater<T>> pq; fill(d + 1, d + n + 1, inf); fill(pr + 1, pr + n + 1, 0); pq.push({d[s] = 0, s}); while (pq.size()) { auto [c, u] = pq.top(); pq.pop(); if (c != d[u]) { continue; } for (auto [v, id] : g[u]) { if (d[v] > d[u] + w[id]) { pr[v] = id; pq.push({d[v] = d[u] + w[id], v}); } } } } void mark() { for (int i = 1; i <= n; ++i) { spec[pr[i]] = 1; } } void solve(int src) { fill(f + 1, f + n + 1, array<int, 2>{inf, inf}); using T = array<int, 3>; priority_queue<T, vector<T>, greater<T>> pq; pq.push({f[src][0] = 0, src, 0}); while (pq.size()) { auto [c, u, type] = pq.top(); pq.pop(); if (f[u][type] != c) { continue; } for (auto [v, id] : g[u]) { if (!spec[id] && f[v][type] > c + w[id]) { pq.push({f[v][type] = c + w[id], v, type}); } } if (!type) { for (auto [v, id] : rg[u]) { if (!spec[id] && f[v][1] > c + w[id] + edges[id][2]) { pq.push({f[v][1] = c + w[id] + edges[id][2], v, 1}); } } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v, c; cin >> u >> v >> w[i] >> c; edges[i] = {u, v, c}; g[u].push_back({v, i}); rg[v].push_back({u, i}); } dijkstra(1, d[0]); mark(); dijkstra(n, d[1]); mark(); auto del = [&](int u, array<int, 2> x) { for (auto &v : g[u]) { if (v == x) { swap(v, g[u].back()); g[u].pop_back(); break; } } }; auto add = [&](int u, array<int, 2> x) { g[u].push_back(x); }; int res = 2 * inf; if (d[0][n] != inf && d[1][1] != inf) { res = d[0][n] + d[1][1]; } solve(1); if (d[1][1] != inf && f[n][1] != inf) { res = min(res, d[1][1] + f[n][1]); } solve(n); if (d[0][n] != inf && f[1][1] != inf) { res = min(res, d[0][n] + f[1][1]); } for (int i = 1; i <= m; ++i) { if (spec[i]) { auto [u, v, c] = edges[i]; del(u, {v, i}); add(v, {u, i}); dijkstra(1, d[0]); dijkstra(n, d[1]); if (d[0][n] != inf && d[1][1] != inf) { res = min(res, d[0][n] + d[1][1] + c); } del(v, {u, i}); add(u, {v, i}); } } cout << (res != 2 * inf ? res : -1); 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...