#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5, BOARD = 505;
int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
int h, w, a, b, c, n, s[N], t[N], nearest[BOARD][BOARD], ans[BOARD][BOARD];
queue<pair<int, int>> bfsQueue;
priority_queue<iii, vector<iii>, greater<iii>> pq;
bool check(int i, int j) {
return i >= 0 && j >= 0 && i < h && j < w;
}
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> h >> w >> a >> b >> c >> n;
h++, w++;
memset(nearest, 63, sizeof nearest);
memset(ans, 63, sizeof ans);
fw (i, 0, n) {
cin >> s[i] >> t[i];
nearest[s[i]][t[i]] = 0;
bfsQueue.push(make_pair(s[i], t[i]));
}
while (!bfsQueue.empty()) {
pair<int, int> curCoords = bfsQueue.front(); bfsQueue.pop();
int curI = curCoords.fi, curJ = curCoords.se;
fw (i, 0, 4) {
int nxtI = curI + dx[i], nxtJ = curJ + dy[i];
if (!check(nxtI, nxtJ)) continue;
if (nearest[nxtI][nxtJ] < nearest[curI][curJ] + 1) continue;
nearest[nxtI][nxtJ] = nearest[curI][curJ] + 1;
bfsQueue.push(make_pair(nxtI, nxtJ));
}
}
//A player will never pick up a ball twice.
//If the ball is at (i, j), it can be assumed the nearest player came and picked it up.
ans[s[0]][t[0]] = 0;
pq.push(iii(0, ii(s[0], t[0])));
//ans[i][j] includes the cost for nearest person to get to the ball.
while (!pq.empty()) {
iii tmp = pq.top(); pq.pop();
int curI = tmp.se.fi, curJ = tmp.se.se;
if (tmp.fi != ans[curI][curJ]) continue;
if (curI == s[n - 1] && curJ == t[n - 1]) {
cout << tmp.fi - c * nearest[curI][curJ] << "\n";
return 0;
}
int curCost = tmp.fi;
fw (i, 0, 4) {
fw (p, 1, max(w, h) + 1) {
int nxtI = curI + p * dx[i], nxtJ = curJ + p * dy[i];
int cost = a * p + b;
if (!check(nxtI, nxtJ)) continue;
if (curCost + cost + c * nearest[nxtI][nxtJ] < ans[nxtI][nxtJ]) {
ans[nxtI][nxtJ] = curCost + cost + c * nearest[nxtI][nxtJ];
pq.push(iii(ans[nxtI][nxtJ], ii(nxtI, nxtJ)));
}
}
int nxtI = curI + dx[i], nxtJ = curJ + dy[i];
if (!check(nxtI, nxtJ)) continue;
if (curCost + c < ans[nxtI][nxtJ]) {
ans[nxtI][nxtJ] = curCost + c;
pq.push(iii(ans[nxtI][nxtJ], ii(nxtI, nxtJ)));
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
734 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
761 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
734 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
