/*input
6 5
1 3 6
3
1 1
0 4
6 5
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define X first
#define Y second
#define mp make_pair
#define int long long
#define N
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
cout << x.fi << sp << x.se << sp;
return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
return os;
}
struct data {
int val, X, Y, mask, dir;
data(int _val, int _X, int _Y, int _mask, int _dir): val(_val), X(_X), Y(_Y), mask(_mask), dir(_dir) {};
};
bool operator < (data a, data b) {
return a.val > b.val;
}
int H, W;
int A, B, C, n;
vector<pair<int, int> > person;
int dp[505][505][4][4];
priority_queue<data> pq;
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void solve() {
// 0 : ball with dir
// 1 : ball only
// 2 : person only
// 3 : both
dp[person[0].X][person[0].Y][3][0] = 0;
pq.push(data(0, person[0].X, person[0].Y, 3, 0));
for (int i = 1; i < person.size(); i++) {
dp[person[i].X][person[i].Y][2][0] = 0;
pq.push(data(0, person[i].X, person[i].Y, 2, 0));
}
while (!pq.empty()) {
data top = pq.top(); pq.pop();
if (dp[top.X][top.Y][top.mask][top.dir] != top.val) continue;
if (top.mask == 2 || top.mask == 3) {
for (int i = 0; i < 4; i++) { // person move
int ax = top.X + dx[i];
int ay = top.Y + dy[i];
if (ax < 1 || ay < 1 || ax > H || ay > W) continue;
if (dp[ax][ay][top.mask][0] > top.val + C) {
dp[ax][ay][top.mask][0] = top.val + C;
pq.push(data(top.val + C, ax, ay, top.mask, 0));
}
}
}
if (top.mask == 3) {
if (dp[top.X][top.Y][2][0] > top.val) { // drop the ball
dp[top.X][top.Y][2][0] = top.val;
pq.push(data(top.val, top.X, top.Y, 2, 0));
}
if (dp[top.X][top.Y][1][0] > top.val) { // drop the ball
dp[top.X][top.Y][1][0] = top.val;
pq.push(data(top.val, top.X, top.Y, 1, 0));
}
for (int i = 0; i < 4; i++) { // kick the ball
if (dp[top.X][top.Y][0][i] > top.val + B) {
dp[top.X][top.Y][0][i] = top.val + B;
pq.push(data(top.val + B, top.X, top.Y, 0, i));
}
}
}
else if (top.mask == 2) {
if (dp[top.X][top.Y][3][0] > dp[top.X][top.Y][2][0] + dp[top.X][top.Y][1][0]) { // grab the ball
dp[top.X][top.Y][3][0] = dp[top.X][top.Y][2][0] + dp[top.X][top.Y][1][0];
pq.push(data(dp[top.X][top.Y][3][0], top.X, top.Y, 3, 0));
}
}
else if (top.mask == 0) {
if (dp[top.X][top.Y][1][0] > dp[top.X][top.Y][0][top.dir]) { // ball stop moving
dp[top.X][top.Y][1][0] = dp[top.X][top.Y][0][top.dir];
pq.push(data(dp[top.X][top.Y][1][0], top.X, top.Y, 1, 0));
}
int ax = top.X + dx[top.dir]; int ay = top.Y + dy[top.dir]; // ball keep moving
if (1 <= ax and ax <= H and 1 <= ay and ay <= W and dp[ax][ay][0][top.dir] > top.val + A) {
dp[ax][ay][0][top.dir] = top.val + A;
pq.push(data(dp[ax][ay][0][top.dir], ax, ay, 0, top.dir));
}
}
}
int ans = 1e18;
for (int x = 1; x <= H; x++) {
for (int y = 1; y <= W; y++) {
int dis = abs(x - person.back().X) + abs(y - person.back().Y);
dis *= C;
ans = min(ans, dis + dp[x][y][1][0]);
}
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> H >> W;
cin >> A >> B >> C;
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
person.push_back(mp(x, y));
}
memset(dp, 60, sizeof(dp));
solve();
}
Compilation message
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
soccer.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
^
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
soccer.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
^
soccer.cpp: In function 'void solve()':
soccer.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < person.size(); i++) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
35056 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
34056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
689 ms |
41780 KB |
Output is correct |
| 2 |
Incorrect |
746 ms |
41780 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
35056 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
34056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
