제출 #516458

#제출 시각아이디문제언어결과실행 시간메모리
516458NachoLibreOlympic Bus (JOI20_ho_t4)C++17
16 / 100
35 ms4428 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() using namespace std; const int inf = 2e9; vector<ll> D(int x, vector<vector<array<int, 3> > > &v, vector<bool> &u, int ub = 0, int bl = 0) { int n = sz(v) - 1; vector<ll> d(n + 1, -1); vector<int> prv(n + 1); vector<int> pre(n + 1); d[x] = 0; set<array<int, 2> > s; s.insert({0, x}); while(sz(s)) { int y = (*s.begin())[1]; s.erase(s.begin()); for(array<int, 3> z : v[y]) { if(z[2] == bl) continue; if(d[z[0]] == -1 || d[z[0]] > d[y] + z[1]) { if(d[z[0]] != -1) { s.erase(s.find({(int)d[z[0]], z[0]})); } d[z[0]] = d[y] + z[1]; prv[z[0]] = y; pre[z[0]] = z[2]; s.insert({(int)d[z[0]], z[0]}); } } } if(ub) { while(prv[ub]) { u[pre[ub]] = 1; ub = prv[ub]; } } for(ll &x : d) { if(x == -1) x = inf; } return d; } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef x freopen("x.txt", "r", stdin); #endif int n, m; cin >> n >> m; vector<vector<array<int, 3> > > v(n + 1); vector<vector<array<int, 3> > > u(n + 1); array<int, 4> x[m + 1]; for(int i = 1; i <= m; ++i) { for(int j = 0; j < 4; ++j) { cin >> x[i][j]; } v[x[i][0]].push_back({x[i][1], x[i][2], i}); u[x[i][1]].push_back({x[i][0], x[i][2], i}); } vector<bool> rlt(m + 1); vector<ll> fro = D(1, v, rlt, n); vector<ll> frn = D(n, v, rlt, 1); vector<ll> too = D(1, u, rlt); vector<ll> ton = D(n, u, rlt); ll fp = fro[n] + frn[1]; for(int i = 1; i <= m; ++i) { ll tp = 0; if(rlt[i]) { v[x[i][1]].push_back({x[i][0], x[i][2], x[i][3]}); tp = x[i][3] + D(1, v, rlt, 0, i)[n] + D(n, v, rlt, 0, i)[1]; v[x[i][1]].pop_back(); } else { tp = x[i][3] + min(fro[n], fro[x[i][1]] + x[i][2] + ton[x[i][0]]) + min(frn[1], frn[x[i][1]] + x[i][2] + too[x[i][0]]); } fp = min(fp, tp); } if(fp > inf) fp = -1; cout << fp << endl; 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...