제출 #661176

#제출 시각아이디문제언어결과실행 시간메모리
661176kinopeOlympic Bus (JOI20_ho_t4)C++14
0 / 100
549 ms14588 KiB
#include <bits/stdc++.h> #define ff first #define ss second using namespace std; typedef long long ll; typedef pair<ll, int> pii; struct st{int a, b; ll c, d;} kraw[50000]; vector<pii> g[201][2]; ll odl[4][201][201]; //0. to z 1 do innych, 1. to z n do innych, 2. to z innych do 1, 3. to z innych do n void dijkstra(int s, int y, int b, bool ODWR){ priority_queue<pii> pq; pq.emplace(0, s); odl[b][s][y] = 0; while(!pq.empty()){ int x = pq.top().ss; ll dis = -pq.top().ff; pq.pop(); for(pii u : g[x][ODWR]){ if(u.ss == y) continue; if(odl[b][u.ss][y] > dis + u.ff){ odl[b][u.ss][y] = dis + u.ff; pq.emplace(-odl[b][u.ss][y], u.ss); } } } } int main(){ int n, m, a, b; ll c, d; scanf("%d%d", &n, &m); for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) odl[0][i][j] = odl[1][i][j] = odl[2][i][j] = odl[3][i][j] = 1e18; for(int i = 0; i < m; ++i){ scanf("%d%d%lld%lld", &a, &b, &c, &d); kraw[i] = {a, b, c, d}; g[a][0].emplace_back(c, b); g[b][1].emplace_back(c, a); } for(int j = 0; j <= n; ++j) odl[0][1][j] = odl[1][n][j] = odl[2][1][j] = odl[3][n][j] = 0; for(int i = 2; i <= n; ++i) {dijkstra(1, i, 0, 0);} dijkstra(1, 0, 0, 0); for(int i = 1; i < n; ++i) {dijkstra(n, i, 1, 0);} dijkstra(n, 0, 1, 0); for(int i = 2; i <= n; ++i) dijkstra(1, i, 2, 1); for(int i = 1; i < n; ++i) dijkstra(n, i, 3, 1); multiset<ll> s[201][4]; //0. to z 1 do x, 1. to z n do x, 2. to z x do 1, 3. to z x do n for(int i = 0; i < m; ++i){ a = kraw[i].a, b = kraw[i].b, c = kraw[i].c; s[b][0].emplace(odl[0][a][b] + c); s[b][1].emplace(odl[1][a][b] + c); s[a][2].emplace(odl[2][b][a] + c); s[a][3].emplace(odl[3][b][a] + c); //printf("%lld %lld %lld %lld\n", odl[0][a][b], odl[1][a][b], odl[2][b][a], odl[3][b][a]); } ll wynik = 1e18; for(int i = 0; i < m; ++i){ a = kraw[i].a, b = kraw[i].b, c = kraw[i].c, d = kraw[i].d; ll tmp = c + odl[0][a][b]; multiset<ll>::iterator it = s[b][0].find(tmp); s[b][0].erase(it); tmp = c + odl[1][a][b]; it = s[b][1].find(tmp); s[b][1].erase(it); tmp = c + d + odl[2][a][b]; s[b][2].emplace(tmp); tmp = c + d + odl[3][a][b]; s[b][3].emplace(tmp); ll t0 = 1e18, t1 = 1e18, t2 = *s[b][2].begin(), t3 = *s[b][3].begin(); if(s[b][0].size()) t0 = *s[b][0].begin(); if(s[b][1].size()) t1 = *s[b][1].begin(); if(b == 1) t0 = t2 = 0; if(b == n) t1 = t3 = 0; wynik = min(wynik, t0 + t3 + t1 + t2); wynik = min(wynik, t0 + t3 + odl[1][1][b]); wynik = min(wynik, odl[0][n][b] + t1 + t2); //printf("%lld %lld %lld %lld\n", t0, t1, t2, t3); tmp = c + d + odl[2][a][b]; it = s[b][2].find(tmp); s[b][2].erase(it); tmp = c + d + odl[3][a][b]; it = s[b][3].find(tmp); s[b][3].erase(it); tmp = c + odl[0][a][b]; s[b][0].emplace(tmp); tmp = c + odl[1][a][b]; s[b][1].emplace(tmp); } wynik = min(wynik, odl[0][n][0] + odl[1][1][0]); if(wynik < 1e18) printf("%lld\n", wynik); else printf("-1"); return 0; }

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d%d%lld%lld", &a, &b, &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...