#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;
const int N = 305;
const double eps = 1e-7;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
return (x > y ? x = y, 1 : 0);
}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
ll d[N][N][5], com[N][N];
int n, h, w;
ll A, B, C;
PR<int> c[200001];
const long long inf = 1e18 + 2;
V<PR<int>> dir{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void solve() {
cin >> h >> w >> A >> B >> C >> n;
forn(i, n) cin >> c[i].ff >> c[i].se;
forn(i, h + 1) forn(j, w + 1) {
com[i][j] = -1;
forn(k, 5) d[i][j][k] = inf;
}
queue<PR<int>> q;
forn(k, n -1) {
auto &[i, j] = c[k];
if(com[i][j] == -1) {
com[i][j] = 0;
q.emplace(i, j);
}
}
while(size(q)) {
auto [i, j] = q.front();
q.pop();
for(auto [di, dj] : dir) {
int x = di + i, y = j + dj;
if(0 <= x && x <= h && 0 <= y && y <= w && com[x][y] == -1) {
com[x][y] = com[i][j] + C;
q.push({x, y});
}
}
}
com[c[n-1].ff][c[n-1].se] = 0;
priority_queue<tuple<ll, int, int, int>> pq;
d[c[0].ff][c[0].se][4] = 0;
pq.push({0, c[0].ff, c[0].se, 4});
auto upd = [&](int i, int j, int t, ll a) {
if(0 <= i && i <= h && 0 <= j && j <= w && a < d[i][j][t]) {
d[i][j][t] = a;
pq.push({-a, i, j, t});
}
};
while(!pq.empty()) {
auto [s, i, j, t] = pq.top();
pq.pop();
s = -s;
//debug(i, j, s);
if(d[i][j][t] < s) continue;
if(t == 4) {
forn(p, 4) {
int x = dir[p].ff + i, y = dir[p].se + j;
upd(i, j, p, s+B);
upd(x, y, 4, s+C);
}
}
else {
int x = dir[t].ff + i, y = dir[t].se + j;
upd(x, y, t, s+A);
upd(i, j, 4, s+com[i][j]);
}
}
cout << d[c[n-1].ff][c[n-1].se][4] << '\n';
}
void test_case() {
int t;
cin >> t;
forn(p, t) {
cout << "Case #" << p + 1 << ": ";
solve();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
69 ms |
6220 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
9300 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
8 ms |
9260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
69 ms |
6220 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
9300 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
