제출 #704861

#제출 시각아이디문제언어결과실행 시간메모리
704861prarieOlympic Bus (JOI20_ho_t4)C++17
100 / 100
152 ms5184 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1E12; int used[50505]; vector<array<int, 4>> edges; vector<ll> dijkstra(int N, int start, vector<vector<array<int, 4>>> &adj, int p = 0) { vector<ll> dist(N, INF); vector<int> check(N, 0); vector<int> prv(N, -1); dist[start] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq; for (int rep = 0; rep < N; rep++) { int cur = -1; ll totalCost = INF; for (int i = 0; i < N; i++) { if (!check[i] && dist[i] < totalCost) { cur = i; totalCost = dist[i]; } } if (cur == -1) { break; } check[cur] = 1; for (auto &[nxt, cst, _, idx] : adj[cur]) { if (dist[nxt] > dist[cur] + cst) { dist[nxt] = dist[cur] + cst; prv[nxt] = idx; } } } if (p && dist[N - 1 - start] != INF) { for (int cur = N - 1 - start; prv[cur] != -1; cur = edges[prv[cur]][0]) { used[prv[cur]] = 1; } } return dist; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); int N, M; cin >> N >> M; vector<vector<array<int, 4>>> adj(N), rev(N); for (int i = 0; i < M; i++) { int x, y, z, w; cin >> x >> y >> z >> w; x--; y--; edges.push_back({ x, y, z, w }); adj[x].push_back({ y, z, w, i }); rev[y].push_back({ x, z, w, i }); } // dist0 : 0 -> i // dist1 : N - 1 - > i // dist2 : i -> 0 // dist3 : i -> N - 1 auto dist0 = dijkstra(N, 0, adj, 1); auto dist1 = dijkstra(N, N - 1, adj, 1); auto dist2 = dijkstra(N, 0, rev); auto dist3 = dijkstra(N, N - 1, rev); const ll ML = 1200000000; ll ans = dist0[N - 1] + dist1[0]; for (int i = 0; i < M; i++) { auto &[u, v, cst, inv] = edges[i]; if (used[i]) { adj[u].erase(find_if(adj[u].begin(), adj[u].end(), [&](const array<int, 4> &x) { return x[3] == i; })); adj[v].push_back({ u, cst, inv, i }); auto p = dijkstra(N, 0, adj); auto q = dijkstra(N, N - 1, adj); adj[u].push_back({ v, cst, inv, i }); adj[v].erase(find_if(adj[v].begin(), adj[v].end(), [&](const array<int, 4> &x) { return x[3] == i; })); ans = min(ans, p[N - 1] + q[0] + inv); continue; } ans = min(ans, min(dist0[N - 1], dist0[v] + dist3[u] + cst) + min(dist1[v] + dist2[u] + cst, dist1[0]) + inv); } if (ans > ML) { cout << -1 << "\n"; } else { cout << ans << "\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...