제출 #631248

#제출 시각아이디문제언어결과실행 시간메모리
631248colossal_pepeOlympic Bus (JOI20_ho_t4)C++17
0 / 100
1097 ms209144 KiB
#include <iostream> #include <vector> #include <queue> #include <tuple> using namespace std; using ll = long long; const ll INF = 1e18; int n, m; vector<tuple<int, int, ll, ll>> edges; vector<vector<int>> g; ll solve() { ll dp[n][m + 1][2]; for (int i = 0; i < n; i++) { for (int j = 0; j <= m; j++) { dp[i][j][0] = dp[i][j][1] = -INF; } } priority_queue<tuple<ll, int, int, bool>> pq; dp[0][0][0] = 0; pq.push({0, 0, 0, 0}); while (not pq.empty()) { auto [dist, u, flipped, returning] = pq.top(); pq.pop(); if (dp[u][flipped][returning] != dist) continue; // cout << u << ' ' << flipped << ' ' << returning << ' ' << dist << endl; for (int e : g[u]) { auto [a, b, c, d] = edges[e]; ll incur = -c; if (flipped == e) swap(a, b); if (dist + incur > dp[b][flipped][returning | b == n - 1]) { dp[b][flipped][returning | b == n - 1] = dist + incur; pq.push({dist + incur, b, flipped, returning | b == n - 1}); } if (flipped or returning) continue; incur = -d; if (dist + incur > dp[u][e][returning]) { dp[u][e][returning] = dist + incur; pq.push({dist + incur, u, e, returning}); } } } ll ans = INF; for (int i = 0; i <= m; i++) { ans = min(ans, -dp[0][i][1]); } return (ans != INF ? ans : -1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; g.resize(n), edges.resize(m + 1); for (int i = 1; i <= m; i++) { auto &[u, v, c, d] = edges[i]; cin >> u >> v >> c >> d; u--, v--; g[u].push_back(i); g[v].push_back(i); } cout << solve() << '\n'; return 0; }

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

ho_t4.cpp: In function 'll solve()':
ho_t4.cpp:34:61: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   34 |             if (dist + incur > dp[b][flipped][returning | b == n - 1]) {
      |                                                           ~~^~~~~~~~
ho_t4.cpp:35:46: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   35 |                 dp[b][flipped][returning | b == n - 1] = dist + incur;
      |                                            ~~^~~~~~~~
ho_t4.cpp:36:66: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   36 |                 pq.push({dist + incur, b, flipped, returning | b == n - 1});
      |                                                                ~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...