제출 #635973

#제출 시각아이디문제언어결과실행 시간메모리
635973ArinoorOlympic Bus (JOI20_ho_t4)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; #define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define pb push_back #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bug(x) cout << #x << " : " << x << '\n' #define bug2(x, y) cout << #x << ' ' << #y << " : " << x << ' ' << y << '\n' typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e2 + 10; const int maxm = 5e4 + 10; const int mod = 1e9 + 7; const int inf = 2e9 + 10; int n, m; int u[maxn], v[maxn], c[maxn], f[maxn]; int d[2][2][maxn][maxn]; int par[2][2][maxn]; bool mark[maxn]; vector<int> G[maxn][2]; int ant(int e, int v){ return ::v[e] + ::u[e] - v; } void dijkstra(int src, bool st, bool eg, int s){ int (&d)[maxn] = ::d[st][eg][s]; int (&p)[maxn] = par[st][eg]; fill_n(d, maxn, inf); memset(mark, 0, sizeof mark); if(!s) memset(p, -1, sizeof p); d[src] = 0; while(true){ int v = -1, h = inf; for(int i = 1; i <= n; i ++) if(!mark[i] and d[i] < h) v = i, h = d[i]; if(v == -1) return; mark[v] = true; for(int e : G[v][eg]){ int u = ant(e, v); int res = min((ll)h + c[e], (ll)inf); if(res < d[u]){ d[u] = res; if(!s) p[u] = e; } } } } int main(){ ios; cin >> n >> m; for(int i = 0; i < m; i ++){ int u, v, c, f; cin >> u >> v >> c >> f; G[u][0].pb(i); G[v][1].pb(i); ::u[i] = u; ::v[i] = v; ::c[i] = c; ::f[i] = f; } for(int i = 0; i <= 1; i ++){ dijkstra(1, 0, i, 0); dijkstra(n, 1, i, 0); } for(int i = 0; i <= 1; i ++){ for(int j = 0; j <= 1; j ++){ for(int v = 1; v <= n; v ++){ int e = par[i][j][v]; if(~e){ int x = c[e]; c[e] = inf; dijkstra(i ? n : 1, i, j, v); c[e] = x; } } } } ll ans = (ll)d[0][0][0][n] + d[1][0][0][1]; for(int i = 0; i < m; i ++){ int u = ::u[i]; int v = ::v[i]; int c = ::c[i]; int f = ::f[i]; int state[2][2]; for(int j = 0; j <= 1; j ++){ state[j][0] = i == par[j][0][v] ? v : 0; state[j][1] = i == par[j][1][u] ? u : 0; } int (&d1_out)[maxn] = d[0][0][state[0][0]]; int (&d1_in)[maxn] = d[0][1][state[0][1]]; int (&dn_out)[maxn] = d[1][0][state[1][0]]; int (&dn_in)[maxn] = d[1][1][state[1][1]]; ll res1 = min((ll)d1_out[n], (ll)d1_out[v] + c + dn_in[u]); ll resn = min((ll)dn_out[1], (ll)dn_out[v] + c + d1_in[u]); ans = min(ans, res1 + resn + f); } if(ans >= inf) ans = -1; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...