제출 #442478

#제출 시각아이디문제언어결과실행 시간메모리
442478Aryan_RainaOlympic Bus (JOI20_ho_t4)C++17
0 / 100
30 ms4544 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t #define ld long double #define ar array mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MOD = 1e9+7; const int INF = 1e15+5; const int MXN = 205, MXM = 50005; vector<ar<int,2>> g[2][MXN]; int a[MXM], b[MXM], w[MXM], revw[MXM], N, M; void dijkstra(int s, int t, int typ, vector<int> &dist, vector<bool> &used) { vector<int> prev(N, -1); used.resize(M, false); dist.resize(N+1, INF); vector<bool> vis(N, false); dist[s] = 0; while (true) { int u = N; for (int i = 0; i < N; i++) if (!vis[i] && dist[i] < dist[u]) u = i; if (u == N) break; for (auto [v, i] : g[typ][u]) if (dist[v] > dist[u] + w[i]) dist[v] = dist[u] + w[i], prev[v] = i; vis[u] = true; } if (typ) return; for (int cur = t; prev[cur] != -1; cur = a[prev[cur]]) used[prev[cur]] = true; } int getdist(int s, int t, int reve) { vector<int> dist(N, INF); vector<bool> vis(N, false); while (true) { int u = N; for (int i = 0; i < N; i++) if (!vis[i] && dist[i] < dist[u]) u = i; if (u == N || dist[t] <= INF/2) break; for (auto [v, i] : g[0][u]) if (i != reve && dist[v] > dist[u] + w[i]) dist[v] = dist[u] + w[i]; if (b[reve] == u) dist[a[reve]] = dist[u] + w[reve]; vis[u] = true; } return dist[t]; } void solve() { cin >> N >> M; for (int i = 0; i < M; i++) { cin >> a[i] >> b[i] >> w[i] >> revw[i]; g[0][--a[i]].push_back({--b[i], i}); g[1][b[i]].push_back({a[i], i}); } vector<int> to1, toN, from1, fromN; vector<bool> used1, usedN, tmp; dijkstra(0, N-1, 0, from1, used1); dijkstra(N-1, 0, 0, fromN, usedN); dijkstra(0, N-1, 1, to1, tmp); dijkstra(N-1, 0, 1, toN, tmp); int ans = from1[N-1] + fromN[0]; for (int i = 0; i < M; i++) { int tmp = revw[i]; if (used1[i]) tmp += getdist(0, N-1, i); else tmp += min(from1[N-1], from1[b[i]] + toN[a[i]] + w[i]); if (usedN[i]) tmp += getdist(N-1, 0, i); else tmp += min(fromN[0], fromN[b[i]] + to1[a[i]] + w[i]); ans = min(ans, tmp); } if (ans >= INF/2) cout << -1 << '\n'; else cout << ans << '\n'; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...