이 제출은 이전 버전의 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, dir;
long long dist;
Data() {}
Data(int u, int v, long long dist, int dir):u(u), v(v), dist(dist), dir(dir) {}
};
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};
long long h, w, a, b, c, n, s[N * N], t[N * N];
long long dis[N][N], f[N][N][5];
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;
FOR(i, 0, h) FOR(j, 0, w) {
dis[i][j] = -1;
REP(k, 5) f[i][j][k] = 1e18;
}
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] + 1;
q.push(v);
}
}
}
f[s[1]][t[1]][4] = 0;
priority_queue<Data, vector<Data>, cmp> heap;
FOR(i, 1, 10) {
heap.push(Data(0, 0, i, 0));
}
FOR(i, 1, 10) {
cerr << heap.top().dist;
heap.pop();
}
heap.push(Data(s[1], t[1], 0, 4));
while (!heap.empty()) {
Data u = heap.top(); heap.pop();
if (u.dist > f[u.u][u.v][u.dir]) continue;
if (u.dir == 4) {
if (u.u == s[n] && u.v == t[n]) {
cout << u.dist << '\n';
return 0;
}
REP(i, 4) {
// Start kicking ball
Data v = Data(u.u + dd[i], u.v + cc[i], u.dist + a + b, i);
if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
f[v.u][v.v][v.dir] = v.dist;
heap.push(v);
}
// Move
v.dist = u.dist + c;
v.dir = 4;
if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
f[v.u][v.v][v.dir] = v.dist;
heap.push(v);
}
}
}
else { // Ball is moving
// Keep moving
Data v = u;
v.u += dd[v.dir],v.v += cc[v.dir];
v.dist += a;
if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
f[v.u][v.v][v.dir] = v.dist;
heap.push(v);
}
//Stop and another player move ball
v = u;
v.dir = 4;
v.dist = u.dist + dis[v.u][v.v] * c;
if (inside(v.u, v.v) && f[v.u][v.v][v.dir] > v.dist) {
f[v.u][v.v][v.dir] = v.dist;
heap.push(v);
}
}
}
#ifdef NERO
double etime = clock();
cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
#endif // NERO
}
컴파일 시 표준 에러 (stderr) 메시지
soccer.cpp: In constructor 'Data::Data(int, int, long long int, int)':
soccer.cpp:19:15: warning: 'Data::dist' will be initialized after [-Wreorder]
long long dist;
^~~~
soccer.cpp:18:15: warning: 'int Data::dir' [-Wreorder]
int u, v, dir;
^~~
soccer.cpp:21:5: warning: when initialized here [-Wreorder]
Data(int u, int v, long long dist, int dir):u(u), v(v), dist(dist), dir(dir) {}
^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |