제출 #779551

#제출 시각아이디문제언어결과실행 시간메모리
7795511binOlympic Bus (JOI20_ho_t4)C++14
0 / 100
33 ms5672 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const ll inf = 1e18; const int MX = 5e4 + 5; ll n, m, a[MX], b[MX], c[MX], d[MX], ans, chk[2][MX], mnd[2], d1, d2, D[4][205]; vector<pair<ll, ll>> adj[205], rev[205]; ll dijk(int s, int e, int f){ int t = n + 1 - s; vector<ll> dist(n + 1, inf); vector<int> E(n + 1, 0), vis(n + 1, 0); dist[s] = 0; while(1){ ll mn = inf, x; for(int i = 1; i <= n; i++) if(!vis[i] && dist[i] < mn) mn = dist[i], x = i; if(mn == inf) break; vis[x] = 1; if(f == 1 || f == 3){ for(auto&[nx, ix] : rev[x]) if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix; } else{ for(auto&[nx, ix] : adj[x]) if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix; } } if(f >= 4){ f -= 4; if(dist[t] == inf) return inf; for(int x = t; x != s; x = a[E[x]]) chk[f][E[x]] = 1; } else if(f >= 0) { for(int i = 1; i <= n; i++) D[f][i] = dist[i]; } return dist[t]; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < m; i++){ cin >> a[i] >> b[i] >> c[i] >> d[i]; adj[a[i]].emplace_back(b[i], i); rev[b[i]].emplace_back(a[i], i); } dijk(1, -1, 0); dijk(n, -1, 1); dijk(n, -1, 2); dijk(1, -1, 3); mnd[0] = dijk(1, -1, 4); mnd[1] = dijk(n, -1, 5); ans = mnd[0] + mnd[1]; for(int i = 0; i < m; i++){ adj[b[i]].emplace_back(a[i], m); c[m] = c[i] + d[i]; if(!chk[0][i]) d1 = min(mnd[0], D[0][b[i]] + c[i] + d[i] + D[1][a[i]]); else d1 = dijk(1, i, -1); if(!chk[1][i]) d2 = min(mnd[1], D[2][b[i]] + c[i] + d[i] + D[3][a[i]]); else d2 = dijk(n, i, -1); //cout << d1 << ' ' << d2 << '\n'; ans = min(ans, d1 + d2); adj[b[i]].pop_back(); } cout << (ans >= inf ? -1 : ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'll dijk(int, int, int)':
ho_t4.cpp:24:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |             for(auto&[nx, ix] : rev[x])
      |                      ^
ho_t4.cpp:28:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |             for(auto&[nx, ix] : adj[x])
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...