Submission #958182

#TimeUsernameProblemLanguageResultExecution timeMemory
958182peterandvoiOlympic Bus (JOI20_ho_t4)C++17
0 / 100
100 ms3408 KiB
#include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif const int N = 205; const int M = 50005; const int INF = (int) 1e9; int n, m; int D[N], d[N][N]; int from[N]; int c[M], cost[M]; bool on_tree[M]; vector<pair<int, int>> g[N]; pair<int, int> edge[M]; void dijkstra(int s, int d[], vector<pair<int, int>> g[N]) { fill(d + 1, d + n + 1, INF); using T = pair<int, int>; priority_queue<T, vector<T>, greater<T>> pq; d[s] = 0; pq.emplace(0, s); while (pq.size()) { auto [x, u] = pq.top(); pq.pop(); if (d[u] == x) { for (auto [v, id] : g[u]) { if (d[v] > x + c[id]) { from[v] = id; pq.emplace(d[v] = x + c[id], v); } } } } for (int i = 1; i <= n; ++i) { on_tree[from[i]] = true; } } int get_dist(int s, int t) { fill(D + 1, D + n + 1, INF); using T = pair<int, int>; priority_queue<T, vector<T>, greater<T>> pq; D[s] = 0; pq.emplace(0, s); while (pq.size()) { auto [x, u] = pq.top(); pq.pop(); if (D[u] == x) { for (auto [v, id] : g[u]) { if (D[v] > x + c[id]) { pq.emplace(D[v] = x + c[id], v); } } } } return D[t]; } void add(int u, int v, int id) { g[u].emplace_back(v, id); } void del(int u, int v, int id) { for (auto &x : g[u]) { if (x == make_pair(v, id)) { swap(x, g[u].back()); g[u].pop_back(); break; } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef ngu freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { d[i][j] = INF; } } for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v >> c[i] >> cost[i]; edge[i] = {u, v}; d[u][v] = min(d[u][v], c[i]); add(u, v, i); } dijkstra(1, D, g); dijkstra(n, D, g); for (int mid = 1; mid <= n; ++mid) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { d[i][j] = min(d[i][j], d[i][mid] + d[mid][j]); } } } int res = d[1][n] + d[n][1]; for (int i = 1; i <= m; ++i) { auto [u, v] = edge[i]; if (on_tree[i]) { del(u, v, i); add(v, u, i); int A = get_dist(1, n); int B = get_dist(n, 1); if (A < INF && B < INF) { res = min(res, A + B + cost[i]); } del(v, u, i); add(u, v, i); } else { int A = min(d[1][n], d[1][v] + c[i] + d[u][n]); int B = min(d[n][1], d[n][v] + c[i] + d[u][1]); if (A < INF && B < INF) { res = min(res, A + B + cost[i]); } } } cout << (res == 2 * INF ? -1 : res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...