Submission #1321641

#TimeUsernameProblemLanguageResultExecution timeMemory
1321641kantaponzSoccer (JOI17_soccer)C++20
0 / 100
3095 ms28792 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll dist[505][505][2][2][2];
int H, W, N;
ll A, B, C;
int tx, ty;
priority_queue<tuple<ll,int,int,bool,bool,bool>> pq;
int xx[] = {0, -1, 0, 1};
int yy[] = {1, 0, -1, 0};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> H >> W >> A >> B >> C >> N;
    for (int i = 0; i < 505; i++) for (int j = 0; j < 505; j++) for (int k=0;k<2;k++) for (int l=0;l<2;l++) for (int m=0;m<2;m++) dist[i][j][k][l][m]=1e18;
    for (int i = 1; i <= N; i++) {
        int y, x;
        cin >> y >> x;
        if (i == 1) {
            dist[y][x][1][1][1] = 0;
            pq.emplace(0, y, x, 1, 1, 1);
        } else if (i == N) {
            ty = y, tx = x;
            dist[y][x][0][0][1] = 0;
            pq.emplace(0, y, x, 0, 0, 1);
        } else {
            dist[y][x][0][0][1] = 0;
            pq.emplace(0, y, x, 0, 0, 1);
        }
    }

    while (!pq.empty()) {
        auto [w, y, x, b, h, p] = pq.top();
        pq.pop();
        w *= -1;
        if (dist[y][x][b][h][p] < w) continue;

        // case 3:
        if (b && h && p) {
            if (dist[y][x][b][!h][p] > w) {
                dist[y][x][b][!h][p] = w;
                pq.emplace(-w, y, x, b, !h, p);
            }
        }

        // case 4:
        if (b && !h && p) {
            if (dist[y][x][b][!h][p] > w) {
                dist[y][x][b][!h][p] = w;
                pq.emplace(-w, y, x, b, h, p);
            }
        }

        // case 2:
        if (p) {
            for (int i = 0; i < 4; i++) {
                int ny = y + yy[i], nx = x + xx[i];
                if (ny < 0 || ny > H || nx < 0 || nx > W) continue;
                // has no ball walk to no ball
                if (!b && !h && dist[ny][nx][0][0][1] > dist[y][x][0][0][1] + C) {
                    dist[ny][nx][0][0][1] = dist[y][x][0][0][1] + C;
                    pq.emplace(-dist[ny][nx][0][0][1], ny, nx, 0, 0, 1);
                }

                // has no ball walk to ball
                if (!b && !h && dist[ny][nx][1][0][1] > dist[y][x][0][0][1] + C + dist[ny][nx][1][0][0]) {
                    dist[ny][nx][1][0][1] = dist[y][x][0][0][1] + C + dist[ny][nx][1][0][0];
                    pq.emplace(-dist[ny][nx][1][0][1], ny, nx, 1, 0, 1);
                }

                // has ball walk while still have the same ball
                if (b && h && dist[ny][nx][1][1][1] > dist[y][x][1][1][1] + C) {
                    dist[ny][nx][1][1][1] = dist[y][x][1][1][1] + C;
                    pq.emplace(-dist[ny][nx][1][1][1], ny, nx, 1, 1, 1);
                }
            }
        }

        // case1 
        for (ll P = 1; P <= max(H, W) + 1; P++) {
            for (int i = 0; i < 4; i++) {
                int ny = y + P*yy[i], nx = x + P*xx[i];
                if (ny < 0 || ny > H || nx < 0 || nx > W) continue;
                ll ww = A * P + B;
                // kick ball to pos with no ppl
                if (b && !h && p && dist[ny][nx][1][0][0] > dist[y][x][1][0][1] + ww) {
                    dist[ny][nx][1][0][0] = dist[y][x][1][0][1] + ww;
                    pq.emplace(-dist[ny][nx][1][0][0], ny, nx, 1, 0, 0);
                }

                // kick ball to pos with ppl
                if (b && !h && p && dist[ny][nx][1][0][1] > w + ww + dist[ny][nx][0][0][1]) {
                    dist[ny][nx][1][0][1] = w + ww + dist[ny][nx][0][0][1];
                    pq.emplace(-dist[ny][nx][1][0][1], ny, nx, 1, 0, 1);
                }
            }
        }
    }

    cout << min(dist[ty][tx][1][1][1], dist[ty][tx][1][0][1]) << endl;

    /*for (int i = 0; i <= H; i++) {
        for (int j = 0; j <= W; j++) {
            cout << dist[i][j][1][1][1] << " ";
        }
        cout << endl;
    }*/
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...