#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
using namespace std;
#define int long long
const vector<int> dx = {0, 0, -1, 1};
const vector<int> dy = {-1, 1, 0, 0};
const int INF = 1e18 + 239;
int h, w;
int gt(int i, int j) {
return i * w + j;
}
pair<int, int> res(int v) {
return {v / w, v % w};
}
int ok(int i, int j) {
return i >= 0 && i < h && j >= 0 && j < w;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int a, b, c, n;
cin >> h >> w >> a >> b >> c >> n;
h++;
w++;
vector<int> s(n);
vector<int> t(n);
for (int i = 0; i < n; i++) {
cin >> s[i] >> t[i];
}
vector<int> nearest(h * w, INF);
{
queue<int> q;
for (int i = 0; i < n; i++) {
nearest[gt(s[i], t[i])] = 0;
q.push(gt(s[i], t[i]));
}
while (!q.empty()) {
int v = q.front();
q.pop();
int i, j;
tie(i, j) = res(v);
for (int k = 0; k < 4; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ok(ni, nj) && nearest[gt(ni, nj)] > nearest[gt(i, j)] + 1) {
nearest[gt(ni, nj)] = nearest[gt(i, j)] + 1;
q.push(gt(ni, nj));
}
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
nearest[gt(i, j)] *= c;
}
}
}
vector<vector<pair<int, int>>> g(2 * h * w);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
g[gt(i, j)].push_back({gt(i, j) + h * w, nearest[gt(i, j)]});
g[gt(i, j) + h * w].push_back({gt(i, j), 0});
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
for (int k = 0; k < 4; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ok(ni, nj)) {
g[gt(i, j) + h * w].push_back({gt(ni, nj) + h * w, c});
}
}
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
for (int tj = 0; tj < w; tj++) {
g[gt(i, j) + h * w].push_back({gt(i, tj), a * abs(j - tj) + b});
}
for (int ti = 0; ti < h; ti++) {
g[gt(i, j) + h * w].push_back({gt(ti, j), a * abs(i - ti) + b});
}
}
}
vector<int> d(2 * h * w, INF);
{
set<pair<int, int>> st;
d[gt(s[0], t[0])] = 0;
st.insert({0, gt(s[0], t[0])});
while (!st.empty()) {
int v = st.begin()->second;
st.erase(st.begin());
for (auto x : g[v]) {
if (d[x.first] > d[v] + x.second) {
st.erase({d[x.first], x.first});
d[x.first] = d[v] + x.second;
st.insert({d[x.first], x.first});
}
}
}
}
cout << d[gt(s[n - 1], t[n - 1])] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
345 ms |
262148 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 |
348 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 |
345 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
