이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//https://oj.uz/problem/view/JOI17_soccer
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 505
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;
struct Data{
int u, v;
long long dist;
Data() {}
Data(int u, int v, long long dist):u(u), v(v), dist(dist) {}
};
struct cmp{
bool operator() (Data a, Data b) {
return a.dist > b.dist;
}
};
const int dd[4] = {1, 0, -1, 0};
const int cc[4] = {0, 1, 0, -1};
int h, w, a, b, c, n, s[N * N], t[N * N];
long long dis[N][N], f[N][N];
bool inside(int i, int j) {
return i >= 0 && j >= 0 && j <= w && i <= h;
}
int main() {
#ifdef NERO
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
double stime = clock();
#else
//freopen(taskname".inp","r",stdin);
//freopen(taskname".out","w",stdout);
#endif //NERO
IO;
cin >> h >> w >> a >> b >> c >> n;
queue<pp> q;
memset(dis, -1, sizeof dis);
FOR(i, 1, n) {
cin >> s[i] >> t[i];
dis[s[i]][t[i]] = 0;
q.push(pp(s[i], t[i]));
}
while (!q.empty()) {
pp u = q.front(); q.pop();
REP(i, 4) {
pp v = pp(u.first + dd[i], u.second + cc[i]);
if (inside(v.first, v.second) && dis[v.first][v.second] == -1) {
dis[v.first][v.second] = dis[u.first][u.second] + c;
q.push(v);
}
}
}
memset(f, 60, sizeof f);
f[s[1]][t[1]] = 0;
priority_queue<Data, vector<Data>, cmp> heap;
heap.push(Data(s[1], t[1], 0));
while (!heap.empty()) {
Data u = heap.top(); heap.pop();
if (u.dist != f[u.u][u.v]) continue;
if (u.u == s[n] && u.v == t[n]) {
cout << u.dist << '\n';
return 0;
}
REP(i, 4) {
// Kick the ball
Data v = u;
v.dist += b;
while (inside(v.u + dd[i], v.v + cc[i])) {
v.u += dd[i], v.v += cc[i];
v.dist += a;
// cout << 'v' << v.u << ' ' << v.v << ' ' << v.dist + dis[v.u][v.v] << '\n';
// cout << f[v.u][v.v] << '\n';
if (f[v.u][v.v] > v.dist + dis[v.u][v.v]) {
f[v.u][v.v] = v.dist + dis[v.u][v.v];
Data newV = v;
newV.dist += dis[v.u][v.v];
heap.push(newV);
}
}
// Move
v.u = u.u + dd[i];
v.v = u.v + cc[i];
v.dist = u.dist + c;
if (inside(v.u, v.v) && f[v.u][v.v] > v.dist) {
f[v.u][v.v] = v.dist;
heap.push(v);
}
}
}
#ifdef NERO
double etime = clock();
cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
#endif // NERO
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |