제출 #36084

#제출 시각아이디문제언어결과실행 시간메모리
36084DoanPhuDucSoccer (JOI17_soccer)C++98
100 / 100
1233 ms32704 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...