Submission #1248435

#TimeUsernameProblemLanguageResultExecution timeMemory
1248435wedonttalkanymoreSoccer (JOI17_soccer)C++20
100 / 100
236 ms22208 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define pii pair<ll, ll> #define fi first #define se second const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 1 << 16; int h, w; int a, b, c, n; int x[N], y[N]; int nxt[505][505]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; struct item { int val, ux, uy; bool operator <(const item &other) const { return val > other.val; } }; void predijkstra() { for (int i = 0; i <= h; i++) { for (int j = 0; j <= w; j++) nxt[i][j] = inf; } priority_queue<item> q; for (int i = 1; i <= n; i++) { q.push({0, x[i], y[i]}); nxt[x[i]][y[i]] = 0; } while (!q.empty()) { auto [val, l, r] = q.top(); q.pop(); if (val > nxt[l][r]) continue; for (int i = 0; i < 4; i++) { int nl = l + dx[i]; int nr = r + dy[i]; if (nl < 0 || nl > h || nr < 0 || nr > w) continue; if (nxt[nl][nr] > nxt[l][r] + 1) { nxt[nl][nr] = nxt[l][r] + 1; q.push({nxt[nl][nr], nl, nr}); } } } } struct node { int val, ux, uy, type; bool operator <(const node &other) const { return val > other.val; } }; int dp[505][505][3]; void dijkstra() { for (int i = 0; i <= h; i++) { for (int j = 0; j <= w; j++) { for (int k = 0; k < 3; k++) dp[i][j][k] = inf; } } dp[x[1]][y[1]][2] = 0; priority_queue<node> q; q.push({0, x[1], y[1], 2}); while (!q.empty()) { auto [val, l, r, type] = q.top(); q.pop(); if (val > dp[l][r][type]) continue; if (dp[l][r][2] > dp[l][r][0] + c * nxt[l][r]) { dp[l][r][2] = dp[l][r][0] + c * nxt[l][r]; q.push({dp[l][r][2], l, r, 2}); } if (dp[l][r][2] > dp[l][r][1] + c * nxt[l][r]) { dp[l][r][2] = dp[l][r][1] + c * nxt[l][r]; q.push({dp[l][r][2], l, r, 2}); } for (int i = 0; i < 4; i++) { int nl = l + dx[i]; int nr = r + dy[i]; if (nl < 0 || nl > h || nr < 0 || nr > w) continue; if (type == 1 && i % 2 == 0 && dp[nl][nr][type] > dp[l][r][type] + a) { dp[nl][nr][type] = dp[l][r][type] + a; q.push({dp[nl][nr][type], nl, nr, type}); } else if (type == 0 && i % 2 == 1 && dp[nl][nr][type] > dp[l][r][type] + a) { dp[nl][nr][type] = dp[l][r][type] + a; q.push({dp[nl][nr][type], nl, nr, type}); } else if (type == 2) { if (dp[l][r][1] > dp[l][r][type] + b) { dp[l][r][1] = dp[l][r][type] + b; q.push({dp[l][r][1], l, r, 1}); } if (dp[l][r][0] > dp[l][r][type] + b) { dp[l][r][0] = dp[l][r][type] + b; q.push({dp[l][r][0], l, r, 0}); } if (dp[nl][nr][2] > dp[l][r][2] + c) { dp[nl][nr][2] = dp[l][r][2] + c; q.push({dp[nl][nr][2], nl, nr, 2}); } } } } int res = min({dp[x[n]][y[n]][0], dp[x[n]][y[n]][1], dp[x[n]][y[n]][2]}); cout << res << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0); if (fopen(".inp", "r")) { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } cin >> h >> w >> a >> b >> c >> n; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i]; } predijkstra(); dijkstra(); return 0; }

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
soccer.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...