This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include <climits>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct edge {
int to;
ll weight;
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int h, w;
cin >> h >> w;
int A, B, C;
cin >> A >> B >> C;
int n;
cin >> n;
vector<pii> pos(n);
vector close(h + 1, vector(w + 1, -1));
queue<pii> Q;
for (int i = 0; i < n; i++) {
cin >> pos[i].first >> pos[i].second;
close[pos[i].first][pos[i].second] = 0;
Q.push(pos[i]);
}
while (!Q.empty()) {
auto [x, y] = Q.front();
Q.pop();
if (x > 0 && close[x - 1][y] == -1) {
close[x - 1][y] = close[x][y] + 1;
Q.push(make_pair(x - 1, y));
}
if (x < h && close[x + 1][y] == -1) {
close[x + 1][y] = close[x][y] + 1;
Q.push(make_pair(x + 1, y));
}
if (y > 0 && close[x][y - 1] == -1) {
close[x][y - 1] = close[x][y] + 1;
Q.push(make_pair(x, y - 1));
}
if (y < w && close[x][y + 1] == -1) {
close[x][y + 1] = close[x][y] + 1;
Q.push(make_pair(x, y + 1));
}
}
vector index(h + 1, vector(w + 1, vector<int>(5, 0)));
int cnt = 0;
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
for (int k = 0; k < 5; k++) {
index[i][j][k] = ++cnt;
}
}
}
vector E(cnt + 5, vector<edge>());
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
E[index[i][j][0]].push_back({.to = index[i][j][1], .weight = B});
E[index[i][j][0]].push_back({.to = index[i][j][2], .weight = B});
E[index[i][j][0]].push_back({.to = index[i][j][3], .weight = B});
E[index[i][j][0]].push_back({.to = index[i][j][4], .weight = B});
E[index[i][j][1]].push_back({.to = index[i][j][0], .weight = close[i][j] * C});
E[index[i][j][2]].push_back({.to = index[i][j][0], .weight = close[i][j] * C});
E[index[i][j][3]].push_back({.to = index[i][j][0], .weight = close[i][j] * C});
E[index[i][j][4]].push_back({.to = index[i][j][0], .weight = close[i][j] * C});
if (i > 0) {
E[index[i][j][0]].push_back({.to = index[i - 1][j][0], .weight = C});
E[index[i][j][1]].push_back({.to = index[i - 1][j][1], .weight = A});
}
if (i < h) {
E[index[i][j][0]].push_back({.to = index[i + 1][j][0], .weight = C});
E[index[i][j][2]].push_back({.to = index[i + 1][j][2], .weight = A});
}
if (j > 0) {
E[index[i][j][0]].push_back({.to = index[i][j - 1][0], .weight = C});
E[index[i][j][3]].push_back({.to = index[i][j - 1][3], .weight = A});
}
if (j < w) {
E[index[i][j][0]].push_back({.to = index[i][j + 1][0], .weight = C});
E[index[i][j][4]].push_back({.to = index[i][j + 1][4], .weight = A});
}
}
}
// for (int i = 1; i <= cnt; i++) {
// cout << "!" << (i - 1) / 5 + 1 << " " << (i - 1) % 5 << endl;
// for (auto [to, weight] : E[i]) {
// cout << (to - 1) / 5 + 1 << " " << (to - 1) % 5 << " " << weight << endl;
// }
// }
vector ans(cnt + 5, (ll)1e18);
int st = index[pos[0].first][pos[0].second][0];
int ed = index[pos[n - 1].first][pos[n - 1].second][0];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> PQ;
ans[st] = 0;
PQ.push(make_pair(0, st));
while (!PQ.empty()) {
auto [dist, cur] = PQ.top();
PQ.pop();
if (ans[cur] < dist) continue;
if (cur == ed) break;
for (auto [to, weight] : E[cur]) {
if (ans[cur] + weight < ans[to]) {
ans[to] = ans[cur] + weight;
PQ.push(make_pair(ans[to], to));
}
}
}
// for (int i = 1; i <= cnt; i++) {
// cout << "#" << (i - 1) / 5 + 1 << " " << (i - 1) % 5 << " " << ans[i] << endl;
// }
cout << ans[ed] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |