Submission #684264

#TimeUsernameProblemLanguageResultExecution timeMemory
684264etheningSoccer (JOI17_soccer)C++17
0 / 100
1012 ms262144 KiB
#include "bits/stdc++.h" #include <climits> #include <queue> #include <utility> using namespace std; using ll = long long; using pii = pair<int, int>; // pii pos[100005]; int close[505][505]; // int dex[505][505][5]; vector<pair<int, ll>> E[753005]; ll ans[753005]; int dex(int x, int y, int z) { return (x * 501 + y) * 3 + z; } int main() { cin.tie(0)->sync_with_stdio(0); int h, w; cin >> h >> w; int A, B, C; cin >> A >> B >> C; int n; cin >> n; memset(close, -1, sizeof(close)); int st, ed; queue<pii> Q; for (int i = 0; i < n; i++) { int tmp, tmp2; cin >> tmp >> tmp2; if (i == 0) { st = dex(tmp, tmp2, 0); } if (i == n - 1) { ed = dex(tmp, tmp2, 0); } close[tmp][tmp2] = 0; Q.push(make_pair(tmp, tmp2)); } while (!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); if (x > 0 && close[x - 1][y] == -1) { close[x - 1][y] = close[x][y] + 1; Q.push(make_pair(x - 1, y)); } if (x < h && close[x + 1][y] == -1) { close[x + 1][y] = close[x][y] + 1; Q.push(make_pair(x + 1, y)); } if (y > 0 && close[x][y - 1] == -1) { close[x][y - 1] = close[x][y] + 1; Q.push(make_pair(x, y - 1)); } if (y < w && close[x][y + 1] == -1) { close[x][y + 1] = close[x][y] + 1; Q.push(make_pair(x, y + 1)); } } for (int i = 0; i <= h; i++) { for (int j = 0; j <= w; j++) { for (int k = 0; k < 3; k++) { ans[dex(i, j, k)] = (ll)1e18; } } } for (int i = 0; i <= h; i++) { for (int j = 0; j <= w; j++) { E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 1), B)); E[dex(i, j, 0)].push_back(make_pair(dex(i, j, 2), B)); E[dex(i, j, 1)].push_back(make_pair(dex(i, j, 0), close[i][j] * C)); E[dex(i, j, 2)].push_back(make_pair(dex(i, j, 0), close[i][j] * C)); if (i > 0) { E[dex(i, j, 0)].push_back(make_pair(dex(i - 1, j, 0), C)); E[dex(i, j, 1)].push_back(make_pair(dex(i - 1, j, 1), A)); } if (i < h) { E[dex(i, j, 0)].push_back(make_pair(dex(i + 1, j, 0), C)); E[dex(i, j, 1)].push_back(make_pair(dex(i + 1, j, 1), A)); } if (j > 0) { E[dex(i, j, 0)].push_back(make_pair(dex(i, j - 1, 0), C)); E[dex(i, j, 2)].push_back(make_pair(dex(i, j - 1, 2), A)); } if (j < w) { E[dex(i, j, 0)].push_back(make_pair(dex(i, j + 1, 0), C)); E[dex(i, j,2)].push_back(make_pair(dex(i, j + 1, 2), A)); } } } // for (int i = 1; i <= cnt; i++) { // cout << "!" << (i - 1) / 5 + 1 << " " << (i - 1) % 5 << endl; // for (auto [to, weight] : E[i]) { // cout << (to - 1) / 5 + 1 << " " << (to - 1) % 5 << " " << weight << endl; // } // } priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> PQ; ans[st] = 0; // cout << st << " " << ed << "!!!" << endl; PQ.push(make_pair(0, st)); while (!PQ.empty()) { auto [dist, cur] = PQ.top(); PQ.pop(); if (ans[cur] < dist) continue; if (cur == ed) break; for (auto [to, weight] : E[cur]) { if (ans[cur] + weight < ans[to]) { ans[to] = ans[cur] + weight; PQ.push(make_pair(ans[to], to)); // cout << cur << " " << to << " " << ans[to] << endl; } } } cout << ans[ed] << endl; }

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:116:3: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |   if (cur == ed) break;
      |   ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...