제출 #563679

#제출 시각아이디문제언어결과실행 시간메모리
5636794fectaOlympic Bus (JOI20_ho_t4)C++17
100 / 100
625 ms7252 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define ld long double #define pii pair<int, int> #define f first #define s second #define boost() cin.tie(0), cin.sync_with_stdio(0) struct edge { int u, v, c, d, i; }; const int MN = 205, MM = 50005; int n, m, u, v, c, d, dist[MN][MN], fw[MM], bw[MM], dis[MN], vis[MN], dd[MN][MN]; vector<edge> a[MN]; edge es[MM]; int dijk(int st, int ed, int blk) { memset(dis, 0x3f, sizeof(dis)); priority_queue<pii, vector<pii >, greater<>> q; dis[st] = 0; q.push({0, st}); while (q.size()) { pii cur = q.top(); q.pop(); if (cur.f > dis[cur.s]) continue; for (edge nxt : a[cur.s]) { if (nxt.i == blk) continue; if (dis[nxt.v] > dis[cur.s] + nxt.c) { dis[nxt.v] = dis[cur.s] + nxt.c; q.push({dis[nxt.v], nxt.v}); } } } return dis[ed]; } int32_t main() { boost(); memset(dist, 0x3f, sizeof(dist)); memset(dd, 0x3f, sizeof(dd)); cin >> n >> m; for (int i = 1; i <= n; i++) dist[i][i] = dd[i][i] = 0; for (int i = 1; i <= m; i++) { cin >> u >> v >> c >> d; dist[u][v] = min(dist[u][v], c); dd[u][v] = 1; es[i] = {u, v, c, d, i}; a[u].push_back({u, v, c, d, i}); } for (int t = 0; t < 5; t++) { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]); } } } } int ans = dist[1][n] + dist[n][1]; if (dist[1][n] < 1e12) { memset(vis, 0, sizeof(vis)); int cur = 1; vis[cur] = 1; while (cur != n) { bool ok = 0; for (edge nxt : a[cur]) { if (dist[1][cur] + nxt.c + dist[nxt.v][n] == dist[1][n] && (nxt.c != 0 || dd[nxt.v][n] + 1 == dd[cur][n])) { fw[nxt.i] = 1; cur = nxt.v; vis[cur] = 1; ok = 1; break; } } assert(ok); } } if (dist[n][1] < 1e12) { memset(vis, 0, sizeof(vis)); int cur = n; vis[cur] = 1; while (cur != 1) { bool ok = 0; for (edge nxt : a[cur]) { if (dist[n][cur] + nxt.c + dist[nxt.v][1] == dist[n][1] && (nxt.c != 0 || dd[nxt.v][1] + 1 == dd[cur][1])) { bw[nxt.i] = 1; cur = nxt.v; vis[cur] = 1; ok = 1; break; } } assert(ok); } } for (int i = 1; i <= m; i++) { int df = dist[1][n]; if (fw[i]) df = dijk(1, n, i); else df = min(df, dist[1][es[i].v] + es[i].c + dist[es[i].u][n]); int db = dist[n][1]; if (bw[i]) db = dijk(n, 1, i); else db = min(db, dist[n][es[i].v] + es[i].c + dist[es[i].u][1]); ans = min(ans, df + db + es[i].d); } printf("%lld\n", ans > 1e12 ? -1 : ans); return 0; } /* 4 4 1 2 0 4 1 3 0 3 4 3 0 2 4 1 0 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...