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>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
const int N = (int) 1e5 + 123;
const int K = 505;
int h, w;
ll a, b, c;
int n;
int x[N], y[N];
int dist[K][K];
ll dp[K][K][2];
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void run() {
cin >> h >> w;
cin >> a >> b >> c;
cin >> n;
rep(i, 0, n) {
cin >> x[i] >> y[i];
}
rep(i, 1, n) {
x[i] -= x[0];
y[i] -= y[0];
}
x[0] = 0;
y[0] = 0;
int mX = *min_element(x, x + n);
int mY = *min_element(y, y + n);
rep(i, 0, n) {
x[i] -= mX;
y[i] -= mY;
}
{
queue<pair<int, int>> q;
rep(i, 0, K) rep(j, 0, K) dist[i][j] = INF;
rep(i, 0, n) {
q.push({x[i], y[i]});
dist[x[i]][y[i]] = 0;
}
while (sz(q)) {
auto v = q.front();
q.pop();
rep(dir, 0, 4) {
int nx = v.first + dx[dir];
int ny = v.second + dy[dir];
if (0 <= nx && nx < K && 0 <= ny && ny < K && mini(dist[nx][ny], dist[v.first][v.second] + 1)) {
q.push({nx, ny});
}
}
}
}
rep(i, 0, K) rep(j, 0, K) rep(t, 0, 2) dp[i][j][t] = LINF;
dp[x[0]][y[0]][1] = 0;
ll ans = LINF;
rep(i, 0, K - 1) {
rep(j, 0, K - 1) {
mini(dp[i][j][1], dp[i][j][0] + dist[i][j] * c);
mini(dp[i + 1][j][1], dp[i][j][1] + c);
mini(dp[i][j + 1][1], dp[i][j][1] + c);
rep(t, 1, K) {
if (i + t >= K) {
break;
}
mini(dp[i + t][j][0], dp[i][j][1] + b + a * t);
}
rep(t, 1, K) {
if (j + t >= K) {
break;
}
mini(dp[i][j + t][0], dp[i][j][1] + b + a * t);
}
rep(t, 0, 2) {
mini(ans, dp[i][j][t] + c * (abs(x[n - 1] - i) + abs(y[n - 1] - j)));
}
}
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |