#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 1 << 16;
int h, w;
int a, b, c, n;
int x[N], y[N];
int nxt[505][505];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
struct item {
int val, ux, uy;
bool operator <(const item &other) const {
return val > other.val;
}
};
void predijkstra() {
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) nxt[i][j] = inf;
}
priority_queue<item> q;
for (int i = 1; i <= n; i++) {
q.push({0, x[i], y[i]});
nxt[x[i]][y[i]] = 0;
}
while (!q.empty()) {
auto [val, l, r] = q.top(); q.pop();
if (val > nxt[l][r]) continue;
for (int i = 0; i < 4; i++) {
int nl = l + dx[i];
int nr = r + dy[i];
if (nl < 0 || nl > h || nr < 0 || nr > w) continue;
if (nxt[nl][nr] > nxt[l][r] + 1) {
nxt[nl][nr] = nxt[l][r] + 1;
q.push({nxt[nl][nr], nl, nr});
}
}
}
}
struct node {
int val, ux, uy, type;
bool operator <(const node &other) const {
return val > other.val;
}
};
int dp[505][505][3];
void dijkstra() {
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
for (int k = 0; k < 3; k++) dp[i][j][k] = inf;
}
}
dp[x[1]][y[1]][2] = 0;
priority_queue<node> q;
q.push({0, x[1], y[1], 2});
while (!q.empty()) {
auto [val, l, r, type] = q.top(); q.pop();
if (val > dp[l][r][type]) continue;
if (dp[l][r][2] > dp[l][r][0] + c * nxt[l][r]) {
dp[l][r][2] = dp[l][r][0] + c * nxt[l][r];
q.push({dp[l][r][2], l, r, 2});
}
if (dp[l][r][2] > dp[l][r][1] + c * nxt[l][r]) {
dp[l][r][2] = dp[l][r][1] + c * nxt[l][r];
q.push({dp[l][r][2], l, r, 2});
}
for (int i = 0; i < 4; i++) {
int nl = l + dx[i];
int nr = r + dy[i];
if (nl < 0 || nl > h || nr < 0 || nr > w) continue;
if (type == 1 && i % 2 == 0 && dp[nl][nr][type] > dp[l][r][type] + a) {
dp[nl][nr][type] = dp[l][r][type] + a;
q.push({dp[nl][nr][type], nl, nr, type});
}
else if (type == 0 && i % 2 == 1 && dp[nl][nr][type] > dp[l][r][type] + a) {
dp[nl][nr][type] = dp[l][r][type] + a;
q.push({dp[nl][nr][type], nl, nr, type});
}
else if (type == 2) {
if (dp[l][r][1] > dp[l][r][type] + b) {
dp[l][r][1] = dp[l][r][type] + b;
q.push({dp[l][r][1], l, r, 1});
}
if (dp[l][r][0] > dp[l][r][type] + b) {
dp[l][r][0] = dp[l][r][type] + b;
q.push({dp[l][r][0], l, r, 0});
}
if (dp[nl][nr][2] > dp[l][r][2] + c) {
dp[nl][nr][2] = dp[l][r][2] + c;
q.push({dp[nl][nr][2], nl, nr, 2});
}
}
}
}
int res = min({dp[x[n]][y[n]][0], dp[x[n]][y[n]][1], dp[x[n]][y[n]][2]});
cout << res << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> h >> w >> a >> b >> c >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
predijkstra();
dijkstra();
return 0;
}
Compilation message (stderr)
soccer.cpp: In function 'int main()':
soccer.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | freopen(".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
soccer.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | freopen(".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |