Submission #827610

#TimeUsernameProblemLanguageResultExecution timeMemory
827610taherOlympic Bus (JOI20_ho_t4)C++17
37 / 100
1079 ms7164 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "C:\GCC\debug.h" #else #define debug(...) void(42) #endif const long long inf = 1165465792545; const int N = 305; vector<array<int, 4>> adj[N], inv[N]; long long d2[N][N], d1[N][N], dist[N]; long long between[N][N]; int count_edges[N][N]; int save_edge[N][N]; int cntA[N], cntB[N], cntC[N], cntD[N]; int middleA[N], middleB[N], middleC[N], middleD[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { between[i][j] = inf; } } vector<array<int, 4>> edges; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; int c, d; cin >> c >> d; --u, --v; adj[u].push_back({v, c, d, i}); inv[v].push_back({u, c, d, i}); edges.push_back({u, v, c, d}); if (between[u][v] > c) { between[u][v] = c; count_edges[u][v] = 1; save_edge[u][v] = i; } else if (between[u][v] == c) { count_edges[u][v] += 1; } } array<int, 2> perm; perm[0] = 0; perm[1] = n - 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d2[i][j] = inf; d1[i][j] = inf; } } auto Floyd = [&]() { for (int i = 0; i < n; i++) { d2[i][i] = 0; d1[i][i] = 0; } for (int i = 0; i < n; i++) { for (auto v : adj[i]) { d2[i][v[0]] = min(d2[i][v[0]], 1LL * v[1]); d1[i][v[0]] = min(d1[i][v[0]], 1LL * (v[1] + 1)); } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]); d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]); } } } }; Floyd(); auto Update = [&](int forbidden, int source, int to, int cost) { for (int i = 0; i < n; i++) { dist[i] = inf; } vector<bool> u(n); dist[perm[1]] = 0; for (int i = 0; i < n; i++) { int v = -1; for (int j = 0; j < n; j++) { if (!u[j] && (v == -1 || dist[j] < dist[v])) { v = j; } } if (v == -1 || dist[v] == inf) { break; } u[v] = true; if (v == source) { if (dist[to] > 1LL * dist[v] + cost) { dist[to] = dist[v] + cost; } } for (auto edge : adj[v]) { if (edge[3] == forbidden) { continue; } if (dist[v] + edge[1] < dist[edge[0]]) { dist[edge[0]] = dist[v] + edge[1]; } } } return dist[perm[0]]; }; for (int i = 0; i < n; i++) { middleA[i] = middleB[i] = middleC[i] = middleD[i] = -1; } for (int i = 0; i < n; i++) { for (auto v : inv[i]) { if (d1[perm[0]][v[0]] + (v[1] + 1) == d1[perm[0]][i]) { cntA[i]++; middleA[i] = v[0]; } } } for (int i = 0; i < n; i++) { for (auto v : adj[i]) { if (d1[v[0]][perm[1]] + (v[1] + 1) == d1[i][perm[1]]) { cntB[i]++; middleB[i] = v[0]; } } } for (int i = 0; i < n; i++) { for (auto v : inv[i]) { if (d1[perm[1]][v[0]] + (v[1] + 1) == d1[perm[1]][i]) { cntC[i]++; middleC[i] = v[0]; } } } for (int i = 0; i < n; i++) { for (auto v : adj[i]) { if (d1[v[0]][perm[0]] + (v[1] + 1) == d1[i][perm[0]]) { cntD[i]++; middleD[i] = v[0]; } } } long long res = inf; res = min(res, d2[perm[0]][perm[1]] + d2[perm[1]][perm[0]]); for (int i = 0; i < m; i++) { int u = edges[i][0]; int v = edges[i][1]; int c = edges[i][2]; int d = edges[i][3]; long long path_from_beg = 0; bool canA = true; bool canB = true; canA &= (cntA[v] > 1 || middleA[v] != u); canB &= (cntB[u] > 1 || middleB[u] != v); if (canA && canB) { path_from_beg = min(d2[perm[0]][perm[1]], d2[perm[0]][v] + d2[u][perm[1]] + c); } else { swap(perm[0], perm[1]); path_from_beg = Update(i, v, u, c); swap(perm[0], perm[1]); } canA = true; canB = true; canA &= (cntC[v] > 1 || middleC[v] != u); canB &= (cntD[u] > 1 || middleD[u] != v); long long path_from_end = 0; if (canA && canB) { path_from_end = min(d2[perm[1]][perm[0]], d2[perm[1]][v] + d2[u][perm[0]] + c); } else { path_from_end = Update(i, v, u, c); } long long tot = path_from_beg + path_from_end + d; res = min(res, tot); } if (res == inf) { cout << -1 << '\n'; } else { cout << res << '\n'; } 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...