제출 #237094

#제출 시각아이디문제언어결과실행 시간메모리
237094wwddOlympic Bus (JOI20_ho_t4)C++14
100 / 100
700 ms7140 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pl; typedef vector<pl> vpl; typedef vector<vpl> al; typedef vector<ll> vl; typedef pair<pl,pl> egg; const ll INFL = 1e18; const int MP = 220; const int MN = 50500; al g,h; vector<vl> ha; vector<egg> eg; vl fist,rist; vl fast,rast; vl pis, ris; vl so; bitset<MN> fs,rs; bitset<MP> fat,rat; void dja(vl& w, vl& pa, int s) { w.assign(g.size(),INFL); pa.assign(g.size(),-1); priority_queue<pl,vpl,greater<pl> > pq; pq.push({0,s}); w[s] = 0; while(!pq.empty()) { pl co = pq.top();pq.pop(); int u = co.second; if(co.first > w[u]) {continue;} for(int i=0;i<g[u].size();i++) { int v = g[u][i].first; ll d = g[u][i].second; if(d+w[u] < w[v]) { w[v] = d+w[u]; int e = ha[u][i]; pa[v] = e; pq.push({w[v],v}); } } } } void djb(vl& w, al& gr, int s) { w.assign(gr.size(),INFL); priority_queue<pl,vpl,greater<pl> > pq; pq.push({0,s}); w[s] = 0; while(!pq.empty()) { pl co = pq.top();pq.pop(); int u = co.second; if(co.first > w[u]) {continue;} for(int i=0;i<gr[u].size();i++) { int v = gr[u][i].first; ll d = gr[u][i].second; if(d+w[u] < w[v]) { w[v] = d+w[u]; pq.push({w[v],v}); } } } } void pre() { dja(fist,pis, 0); dja(rist,ris, g.size()-1); djb(fast,h,g.size()-1); djb(rast,h,0); int pp = g.size()-1; while(pis[pp] != -1) { fat.set(pp); fs.set(pis[pp]); pp = eg[pis[pp]].first.first; } fat.set(0); for(int i=0;i<ris.size();i++) { if(ris[i] != -1) { rs.set(ris[i]); } } pp = 0; while(ris[pp] != -1) { rat.set(pp); rs.set(ris[pp]); pp = eg[ris[pp]].first.first; } rat.set(g.size()-1); } ll proc(int e) { vl tp; int u = eg[e].first.first; int v = eg[e].first.second; ll ex = eg[e].second.second; ll reg = eg[e].second.first; int eid = so[e]; ll fdi,rdi; if(fs[e]) { g[u][eid].second = INFL; g[v].push_back({u,reg}); djb(tp,g,0); fdi = tp[g.size()-1]; g[v].pop_back(); g[u][eid].second = reg; } else { fdi = fist[g.size()-1]; fdi = min(fdi,fist[v]+fast[u]+reg); } if(rs[e]) { g[u][eid].second = INFL; g[v].push_back({u,reg}); djb(tp,g,g.size()-1); rdi = tp[0]; g[v].pop_back(); g[u][eid].second = reg; } else { rdi = rist[0]; rdi = min(rdi,rist[v]+rast[u]+reg); } return fdi+rdi+ex; } int main() { ios::sync_with_stdio(0);cin.tie(0); ll n,m; cin >> n >> m; g.assign(n,vpl()); h.assign(n,vpl()); ha.assign(n,vl()); fist.assign(n,INFL); rist.assign(n,INFL); for(int i=0;i<m;i++) { ll a,b,c,d; cin >> a >> b >> c >> d; a--;b--; so.push_back(g[a].size()); g[a].push_back({b,c}); h[b].push_back({a,c}); ha[a].push_back(i); eg.push_back({{a,b},{c,d}}); } pre(); ll res = fist[n-1]+rist[0]; for(int i=0;i<m;i++) { res = min(res,proc(i)); } if(res >= INFL) { cout << -1 << '\n'; } else { cout << res << '\n'; } }

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

ho_t4.cpp: In function 'void dja(vl&, vl&, int)':
ho_t4.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) {
               ~^~~~~~~~~~~~
ho_t4.cpp: In function 'void djb(vl&, al&, int)':
ho_t4.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gr[u].size();i++) {
               ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void pre()':
ho_t4.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ris.size();i++) {
              ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...