| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684271 |
2023-01-20T19:22:43 Z |
ethening |
Soccer (JOI17_soccer) |
C++17 |
|
955 ms |
262144 KB |
#include "bits/stdc++.h"
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];
queue<pii> Q;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> PQ;
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;
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)].reserve(6);
E[dex(i, j, 1)].reserve(3);
E[dex(i, j, 2)].reserve(3);
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;
// }
// }
ans[st] = 0;
// cout << st << " " << ed << "!!!" << endl;
PQ.push(make_pair(0, st));
while (!PQ.empty()) {
pair<ll, int> x = PQ.top();
PQ.pop();
if (ans[x.second] < x.first) continue;
if (x.second == ed) break;
for (const pair<int, ll>& y: E[x.second]) {
if (ans[x.second] + y.second < ans[y.first]) {
ans[y.first] = ans[x.second] + y.second;
PQ.push(make_pair(ans[y.first], y.first));
// cout << cur << " " << to << " " << ans[to] << endl;
}
}
}
cout << ans[ed] << endl;
}
Compilation message
soccer.cpp: In function 'int main()':
soccer.cpp:117:3: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | if (x.second == ed) break;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
36956 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19028 KB |
Output is correct |
| 3 |
Runtime error |
938 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
955 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
36956 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19028 KB |
Output is correct |
| 3 |
Runtime error |
938 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
