제출 #209014

#제출 시각아이디문제언어결과실행 시간메모리
209014eriksuenderhaufOlympic Bus (JOI20_ho_t4)C++11
100 / 100
65 ms8108 KiB
#include <bits/stdc++.h> #define pb push_back #define sz(x) (int)(x).size() #define trav(x, a) for (const auto& x: a) #define pii pair<int,int> #define st first #define nd second using namespace std; typedef long long ll; const int N = 5e4 + 5; const ll inf = 0x1f1f1f1f1f1f1f1f; vector<int> e[2][N], adj[N]; int U[N], V[N], C[N], D[N]; ll dp[2][2][N], dp2[2][205][205]; int n, m, par[2][2][N]; int mrk[2][2][N]; vector<int> path[2][2]; void solve(int s, int t, int i) { priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push({0, s}); for (int j = 1; j <= n; j++) dp[i][s>1][j] = inf; dp[i][s>1][s] = 0; while (!pq.empty()) { auto c = pq.top(); pq.pop(); if (dp[i][s>1][c.nd] != c.st) continue; for (int j: e[i][c.nd]) { int v = U[j]^V[j]^c.nd; if (dp[i][s>1][v] > c.st + C[j]) { dp[i][s>1][v] = c.st + C[j]; par[i][s>1][v] = j; pq.push({dp[i][s>1][v], v}); } } } if (dp[i][s>1][t] == inf) return; int u = t; while (u != s) { int j = par[i][s>1][u]; mrk[i][s>1][j] = 1; path[i][s>1].pb(u); u = U[j]^V[j]^u; } path[i][s>1].pb(u); reverse(path[i][s>1].begin(), path[i][s>1].end()); } ll calc(int j, int i) { int mi = n+1; for (int l = 0; l+1 < sz(path[0][j]); l++) { if (U[i] == path[0][j][l] && path[0][j][l+1] == V[i]) { mi = l; break; } } ll ret = inf; for (int l = 0; l <= mi; l++) for (int r = mi+1; r < sz(path[0][j]); r++) ret = min(ret, dp[0][j][path[0][j][l]] + dp2[j][path[0][j][l]][path[0][j][r]] + dp[1][j^1][path[0][j][r]]); return ret; } int main() { memset(dp, 0x1f, sizeof dp); memset(dp2, 0x1f, sizeof dp2); scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %d %d", U+i, V+i, C+i, D+i); e[0][U[i]].pb(i); e[1][V[i]].pb(i); } for (int i = 0; i < 2; i++) { solve(1, n, i); solve(n, 1, i); } for (int t = 0; t < 2; t++) { for (int i = 1; i <= m; i++) if (!mrk[0][t][i]) dp2[t][U[i]][V[i]] = min(dp2[t][U[i]][V[i]], 1ll*C[i]); for (int i = 1; i <= n; i++) dp2[t][i][i] = 0; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp2[t][i][j] = min(dp2[t][i][j], dp2[t][i][k] + dp2[t][k][j]); } ll x1 = dp[0][0][n], x2 = dp[0][1][1]; ll ans = x1 + x2; for (int i = 1; i <= m; i++) { bool f1 = mrk[0][0][i], f2 = mrk[0][1][i]; ll c1 = min(x1, dp[0][0][V[i]] + C[i] + dp[1][1][U[i]]); ll c2 = min(x2, dp[0][1][V[i]] + C[i] + dp[1][0][U[i]]); if (f1 && f2) ans = min(ans, calc(0,i) + calc(1,i) + D[i]); else if (f1) ans = min(ans, calc(0,i) + c2 + D[i]); else if (f2) ans = min(ans, calc(1,i) + c1 + D[i]); else ans = min(ans, c1 + c2 + D[i]); } if (ans >= inf) ans = -1; printf("%I64d\n", ans); }

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:106:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
   printf("%I64d\n", ans);
                        ^
ho_t4.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", U+i, V+i, C+i, D+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...