제출 #393624

#제출 시각아이디문제언어결과실행 시간메모리
39362479brueOlympic Bus (JOI20_ho_t4)C++14
100 / 100
153 ms8388 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Edge{ int u, v, idx; ll c, d; Edge(){} Edge(int u, int v, int idx, ll c, ll d): u(u), v(v), idx(idx), c(c), d(d){} bool operator==(const Edge &r)const{ return idx == r.idx; } }; int n, m; vector<Edge> link[202]; vector<Edge> revLink[202]; Edge arr[50002]; ll ans = LLONG_MAX; struct Dijkstra { int n; ll dist[202]; int prv[202], start, last; bool used[50002], chk[202]; void init(int _n, int _start){ n = _n, start = _start, last = n+1-start; } void run(){ fill(dist+1, dist+n+1, 1e18); fill(chk+1, chk+n+1, false); fill(used+1, used+m+1, false); dist[start] = 0; while(1){ int pnt = 0; ll pntD = 1e18; for(int i=1; i<=n; i++){ if(!chk[i] && pntD > dist[i]) pntD = dist[i], pnt = i; } if(pnt == 0) break; chk[pnt] = 1; for(auto y: link[pnt]){ int nxt = y.v; ll nxtCost = dist[pnt] + y.c; if(nxtCost < dist[nxt]){ dist[nxt] = nxtCost; prv[nxt] = y.idx; } } } if(dist[last] == 1e18) return; int tmp = last; while(tmp != start){ used[prv[tmp]] = 1; tmp = arr[prv[tmp]].u; } } } dijk1, dijk2, dijktmp, dijk1rev, dijk2rev; int main(){ scanf("%d %d", &n, &m); for(int i=1; i<=m; i++){ int u, v; ll c, d; scanf("%d %d %lld %lld", &u, &v, &c, &d); link[u].push_back(Edge(u, v, i, c, d)); revLink[v].push_back(Edge(v, u, i, c, d)); arr[i] = Edge(u, v, i, c, d); } dijk1.init(n, 1), dijk1rev.init(n, n), dijk2.init(n, n), dijk2rev.init(n, 1); dijk1.run(), dijk2.run(); ans = dijk1.dist[n] + dijk2.dist[1]; for(int i=1; i<=n; i++) revLink[i].swap(link[i]); for(int i=1; i<=m; i++) swap(arr[i].u, arr[i].v); dijk1rev.run(); dijk2rev.run(); for(int i=1; i<=n; i++) revLink[i].swap(link[i]); for(int i=1; i<=m; i++) swap(arr[i].u, arr[i].v); for(int i=1; i<=m; i++){ ll ret = arr[i].d; if(!dijk1.used[i]) ret += min(dijk1.dist[n], dijk1.dist[arr[i].v] + dijk1rev.dist[arr[i].u] + arr[i].c); else{ link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i])); swap(arr[i].u, arr[i].v); link[arr[i].u].push_back(arr[i]); dijktmp.init(n, 1); dijktmp.run(); ret += dijktmp.dist[n]; link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i])); swap(arr[i].u, arr[i].v); link[arr[i].u].push_back(arr[i]); } if(!dijk2.used[i]) ret += min(dijk2.dist[1], dijk2.dist[arr[i].v] + dijk2rev.dist[arr[i].u] + arr[i].c); else{ link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i])); swap(arr[i].u, arr[i].v); link[arr[i].u].push_back(arr[i]); dijktmp.init(n, n); dijktmp.run(); ret += dijktmp.dist[1]; link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i])); swap(arr[i].u, arr[i].v); link[arr[i].u].push_back(arr[i]); } ans = min(ans, ret); } printf("%lld", ans > 1e17 ? -1 : ans); }

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%d %d %lld %lld", &u, &v, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...