#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(ii(s[i], t[i]));
}
while (!bfsQueue.empty()) {
ii 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;
// cout << "Fix " << nxtI << " " << nxtJ << " old nearest = " << nearest[nxtI][nxtJ] << " cur nearest = " << nearest[curI][curJ] << "\n";
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;
// cout << "CurI = " << curI << " curJ = " << curJ << "\n";
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
6004 KB |
Output is correct |
2 |
Correct |
7 ms |
4920 KB |
Output is correct |
3 |
Correct |
245 ms |
10768 KB |
Output is correct |
4 |
Correct |
64 ms |
7536 KB |
Output is correct |
5 |
Correct |
421 ms |
7664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
7680 KB |
Output is correct |
2 |
Correct |
22 ms |
6048 KB |
Output is correct |
3 |
Correct |
318 ms |
10716 KB |
Output is correct |
4 |
Correct |
2170 ms |
10612 KB |
Output is correct |
5 |
Correct |
380 ms |
10772 KB |
Output is correct |
6 |
Correct |
662 ms |
10732 KB |
Output is correct |
7 |
Correct |
41 ms |
10884 KB |
Output is correct |
8 |
Correct |
50 ms |
10788 KB |
Output is correct |
9 |
Correct |
33 ms |
7808 KB |
Output is correct |
10 |
Correct |
51 ms |
6164 KB |
Output is correct |
11 |
Correct |
90 ms |
10916 KB |
Output is correct |
12 |
Correct |
174 ms |
10772 KB |
Output is correct |
13 |
Correct |
455 ms |
10732 KB |
Output is correct |
14 |
Correct |
37 ms |
10784 KB |
Output is correct |
15 |
Correct |
17 ms |
6192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
6004 KB |
Output is correct |
2 |
Correct |
7 ms |
4920 KB |
Output is correct |
3 |
Correct |
245 ms |
10768 KB |
Output is correct |
4 |
Correct |
64 ms |
7536 KB |
Output is correct |
5 |
Correct |
421 ms |
7664 KB |
Output is correct |
6 |
Correct |
42 ms |
7680 KB |
Output is correct |
7 |
Correct |
22 ms |
6048 KB |
Output is correct |
8 |
Correct |
318 ms |
10716 KB |
Output is correct |
9 |
Correct |
2170 ms |
10612 KB |
Output is correct |
10 |
Correct |
380 ms |
10772 KB |
Output is correct |
11 |
Correct |
662 ms |
10732 KB |
Output is correct |
12 |
Correct |
41 ms |
10884 KB |
Output is correct |
13 |
Correct |
50 ms |
10788 KB |
Output is correct |
14 |
Correct |
33 ms |
7808 KB |
Output is correct |
15 |
Correct |
51 ms |
6164 KB |
Output is correct |
16 |
Correct |
90 ms |
10916 KB |
Output is correct |
17 |
Correct |
174 ms |
10772 KB |
Output is correct |
18 |
Correct |
455 ms |
10732 KB |
Output is correct |
19 |
Correct |
37 ms |
10784 KB |
Output is correct |
20 |
Correct |
17 ms |
6192 KB |
Output is correct |
21 |
Correct |
717 ms |
201576 KB |
Output is correct |
22 |
Correct |
1063 ms |
16880 KB |
Output is correct |
23 |
Correct |
1322 ms |
29244 KB |
Output is correct |
24 |
Correct |
868 ms |
17180 KB |
Output is correct |
25 |
Correct |
749 ms |
10768 KB |
Output is correct |
26 |
Correct |
1326 ms |
17308 KB |
Output is correct |
27 |
Runtime error |
1670 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
28 |
Halted |
0 ms |
0 KB |
- |