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>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<ll,int,int,int>;
const ll inf = 1e13 + 5;
const int nmax = 505;
int H, w;
int A, B, C;
ll mat[nmax][nmax][5];
ll dist[nmax][nmax];
int dirx[4] = {1, -1, 0, 0};
int diry[4] = {0, 0, 1, -1};
signed main() {
cin >> H >> w;
cin >> A >> B >> C;
++H;
++w;
for(int i = 1; i <= H; i++) {
for(int j = 1; j <= w; j++) {
dist[i][j] = inf;
for(int h = 0; h < 5; h++)
mat[i][j][h] = inf;
}
}
int q;
cin >> q;
int ss = 1, ts = 1, sf = 1, tf = 1;
queue<pii> que;
for(int i = 0, x, y; i < q; i++) {
cin >> x >> y;
++x;
++y;
dist[x][y] = 0;
que.emplace(x, y);
if(i == 0)
tie(ss, ts) = pii{x, y};
tie(sf, tf) = pii{x, y};
}
while(!que.empty()) {
auto [x, y] = que.front();
que.pop();
for(int h = 0; h < 4; h++) {
if(dist[x + dirx[h]][y + diry[h]] > dist[x][y] + C) {
que.emplace(x + dirx[h], y + diry[h]);
dist[x + dirx[h]][y + diry[h]] = dist[x][y] + C;
}
}
}
priority_queue<tiii, vector<tiii>, greater<tiii>> heap;
heap.emplace(0, ss, ts, 4);
mat[ss][ts][4] = 0;
while(!heap.empty()) {
auto [cost, x, y, mode] = heap.top();
heap.pop();
//if(mode != 4)
//cerr << "> " << mat[x][y][mode] << "==" << cost << ' ' << x << ' ' << y << ' ' << mode << '\n';
if(cost > mat[x][y][mode]) continue;
//if(mode != 4)
//cerr << cost << ' ' << x << ' ' << y << ' ' << mode << '\n';
if(mode == 4) {
for(int h = 0; h < 4; h++) {
if(mat[x + dirx[h]][y + diry[h]][mode] > mat[x][y][mode] + C) {
mat[x + dirx[h]][y + diry[h]][mode] = mat[x][y][mode] + C;
//cerr << "+ " << x + dirx[h] << ' ' << y + diry[h] << ' ' << mode << '\n';
heap.emplace(mat[x][y][mode] + C, x + dirx[h], y + diry[h], mode);
}
if(mat[x][y][h] > mat[x][y][mode] + B) {
//cerr << "+ " << x << ' ' << y << ' ' << h << '\n';
mat[x][y][h] = mat[x][y][mode] + B;
heap.emplace(mat[x][y][h], x, y, h);
}
}
}
else {
if(mat[x + dirx[mode]][y + diry[mode]][mode] > mat[x][y][mode] + A) {
mat[x + dirx[mode]][y + diry[mode]][mode] = mat[x][y][mode] + A;
//cerr << "+ " << x + dirx[mode] << ' ' << y + diry[mode] << ' ' << mode << '\n';
heap.emplace(mat[x][y][mode] + A, x + dirx[mode], y + diry[mode], mode);
}
if(mat[x][y][4] > mat[x][y][mode] + dist[x][y]) {
mat[x][y][4] = mat[x][y][mode] + dist[x][y];
heap.emplace(mat[x][y][4], x, y, 4);
}
}
}
ll mn = inf;
for(int h = 0; h < 5; h++)
mn = min(mat[sf][tf][h], mn);
cout << mn << '\n';
}
/**
Vom spune că toamna a venit... foarte trist -
-- George Bacovia, Scântei galbene
*/
Compilation message (stderr)
soccer.cpp: In function 'int main()':
soccer.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto [x, y] = que.front();
| ^
soccer.cpp:72:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | auto [cost, x, y, mode] = heap.top();
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |