이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
using namespace std;
typedef long long LL;
const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
int dx[] = {+0, -1, +0, +1};
int dy[] = {-1, +0, +1, +0};
int n, m, q, A, B, C, sx, sy, tx, ty;
int g[N][N];
int f[4][N][N];
LL d[N][N][5];
struct State {
int x, y, z;
LL w;
State () {}
State (int x, int y, int z, LL w) : x(x), y(y), z(z), w(w) {}
bool operator < (const State &that) const {
if (w != that.w) return w < that.w;
if (z != that.z) return z < that.z;
if (x != that.x) return x < that.x;
return y < that.y;
}
};
set <State> S;
void Init() {
FOR(i, 0, n)
FOR(j, 0, m) {
if (i - 1 >= 0) f[0][i][j] = min(f[0][i][j], f[0][i - 1][j] + 1);
if (j - 1 >= 0) f[0][i][j] = min(f[0][i][j], f[0][i][j - 1] + 1);
}
FOR(i, 0, n)
FOD(j, m, 0) {
if (j + 1 <= m) f[1][i][j] = min(f[1][i][j], f[1][i][j + 1] + 1);
if (i - 1 >= 0) f[1][i][j] = min(f[1][i][j], f[1][i - 1][j] + 1);
}
FOD(i, n, 0)
FOD(j, m, 0) {
if (i + 1 <= n) f[2][i][j] = min(f[2][i][j], f[2][i + 1][j] + 1);
if (j + 1 <= m) f[2][i][j] = min(f[2][i][j], f[2][i][j + 1] + 1);
}
FOD(i, n, 0)
FOR(j, 0, m) {
if (i + 1 <= n) f[3][i][j] = min(f[3][i][j], f[3][i + 1][j] + 1);
if (j - 1 <= m) f[3][i][j] = min(f[3][i][j], f[3][i][j - 1] + 1);
}
FOR(i, 0, n)
FOR(j, 0, m)
FOR(k, 0, 3) g[i][j] = min(g[i][j], f[k][i][j]);
}
bool Inside(int x, int y) {
return 0 <= x && x <= n && 0 <= y && y <= m;
}
void Push(int u, int v, int k, int x, int y, int z, LL w) {
if (d[u][v][k] > d[x][y][z] + w) {
S.erase(State(u, v, k, d[u][v][k]));
d[u][v][k] = d[x][y][z] + w;
S.insert(State(u, v, k, d[u][v][k]));
}
}
void Dijkstra() {
memset(d, INFL, sizeof d);
d[sx][sy][4] = 0; S.insert(State(sx, sy, 4, d[sx][sy][4]));
while (S.size()) {
int x = S.begin() -> x, y = S.begin() -> y, z = S.begin() -> z;
S.erase(S.begin());
if (z == 4) {
FOR(k, 0, 3) {
int u = x + dx[k], v = y + dy[k];
if (Inside(u, v)) {
Push(u, v, k, x, y, z, A + B);
Push(u, v, 4, x, y, z, C);
}
}
} else {
int u = x + dx[z], v = y + dy[z];
if (Inside(u, v)) Push(u, v, z, x, y, z, A);
Push(x, y, 4, x, y, z, (LL)g[x][y] * C);
}
}
LL ans = INFL;
FOR(k, 0, 4) ans = min(ans, d[tx][ty][k]);
printf("%lld", ans);
}
int main() {
// freopen("SOCCER.INP", "r", stdin);
// freopen("SOCCER.OUT", "w", stdout);
scanf("%d%d", &n, &m);
scanf("%d%d%d", &A, &B, &C);
scanf("%d", &q);
memset(f, INF, sizeof f);
memset(g, INF, sizeof g);
scanf("%d%d", &sx, &sy);
FOR(i, 2, q - 1) {
int x, y; scanf("%d%d", &x, &y);
FOR(k, 0, 3) f[k][x][y] = 0;
}
scanf("%d%d", &tx, &ty);
Init();
Dijkstra();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
soccer.cpp: In function 'void Dijkstra()':
soccer.cpp:81:29: warning: overflow in implicit constant conversion [-Woverflow]
memset(d, INFL, sizeof d);
^
soccer.cpp: In function 'int main()':
soccer.cpp:108:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
soccer.cpp:109:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &A, &B, &C);
^
soccer.cpp:110:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
soccer.cpp:113:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &sx, &sy);
^
soccer.cpp:115:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
^
soccer.cpp:118:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &tx, &ty);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |