| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1066242 |
2024-08-19T16:53:17 Z |
sammyuri |
Soccer (JOI17_soccer) |
C++17 |
|
1691 ms |
70112 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dist[505][505];
ll dist_2[505][505];
ll a, b, c;
ll calc_cost(ll dx, ll dy) {
ll best = (dx + dy) * c;
best = min(best, dx * c + b + dy * a);
best = min(best, dy * c + b + dx * a);
return best;
}
int main() {
memset(dist, -1, sizeof(dist));
int h, w; cin >> h >> w;
h ++; w ++;
cin >> a >> b >> c;
vector<pair<int, int>> players;
int n; cin >> n;
int starti, startj, endi, endj;
for (int i = 0; i < n; i ++) {
int s, t; cin >> s >> t;
players.push_back({s, t});
if (i == 0)
starti = s, startj = t;
else if (i == n - 1)
endi = s, endj = t;
}
// multisource bfs
queue<pair<int, int>> q;
for (auto a : players) {
dist[a.first][a.second] = 0;
q.push(a);
}
while (q.size()) {
pair<int, int> cur = q.front(); q.pop();
int curdist = dist[cur.first][cur.second];
if (cur.first > 0 && dist[cur.first - 1][cur.second] == -1) {
q.push({cur.first - 1, cur.second});
dist[cur.first - 1][cur.second] = curdist + 1;
}
if (cur.first < h - 1 && dist[cur.first + 1][cur.second] == -1) {
q.push({cur.first + 1, cur.second});
dist[cur.first + 1][cur.second] = curdist + 1;
}
if (cur.second > 0 && dist[cur.first][cur.second - 1] == -1) {
q.push({cur.first, cur.second - 1});
dist[cur.first][cur.second - 1] = curdist + 1;
}
if (cur.second < w - 1 && dist[cur.first][cur.second + 1] == -1) {
q.push({cur.first, cur.second + 1});
dist[cur.first][cur.second + 1] = curdist + 1;
}
}
// calculate answer
priority_queue<pair<ll, pair<int, int>>> pq;
for (int i = 0; i < h; i ++)
for (int j = 0; j < w; j ++) {
// initial distance
ll curdist = calc_cost(abs(i - starti), abs(j - startj));
curdist += dist[i][j] * c;
dist_2[i][j] = curdist;
pq.push({-curdist, {i, j}});
}
ll best = 1e9;
while (pq.size()) {
auto cur = pq.top(); pq.pop();
ll curdist = -cur.first;
int i = cur.second.first, j = cur.second.second;
if (dist_2[i][j] != curdist)
continue;
// send straight to finish
// cout << curdist << " " << i << " " << j << endl;
best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
for (int ii = 0; ii < h; ii ++) {
ll newdist = curdist + calc_cost(abs(ii - i), 0) + dist[ii][j] * c;
if (dist_2[ii][j] > newdist) {
dist_2[ii][j] = newdist;
pq.push({-newdist, {ii, j}});
}
}
for (int jj = 0; jj < h; jj ++) {
ll newdist = curdist + calc_cost(abs(jj - j), 0) + dist[i][jj] * c;
if (dist_2[i][jj] > newdist) {
dist_2[i][jj] = newdist;
pq.push({-newdist, {i, jj}});
}
}
}
cout << best << endl;
return 0;
}
Compilation message
soccer.cpp: In function 'int main()':
soccer.cpp:77:67: warning: 'endj' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
| ~~^~~~~~
soccer.cpp:77:52: warning: 'endi' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | best = min(best, curdist + calc_cost(abs(i - endi), abs(j - endj)));
| ~~^~~~~~
soccer.cpp:23:17: warning: 'startj' may be used uninitialized in this function [-Wmaybe-uninitialized]
23 | int starti, startj, endi, endj;
| ^~~~~~
soccer.cpp:23:9: warning: 'starti' may be used uninitialized in this function [-Wmaybe-uninitialized]
23 | int starti, startj, endi, endj;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
22932 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Incorrect |
1691 ms |
70112 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
949 ms |
14024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
22932 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Incorrect |
1691 ms |
70112 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
