제출 #1302129

#제출 시각아이디문제언어결과실행 시간메모리
1302129itachi_godSoccer (JOI17_soccer)C++20
100 / 100
245 ms18220 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

using ll = long long;
const ll INF = 1e18;

int H, W;
ll A, B, C;
int N;
vector<pair<int, int>> players;
ll pickup[505][505];
ll dist[505][505][3];

int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};

bool inside(int r, int c) {
    return r >= 0 && r <= H && c >= 0 && c <= W;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> H >> W;
    cin >> A >> B >> C;
    cin >> N;

    players.resize(N);
    for (int i = 0; i <= H; i++) {
        for (int j = 0; j <= W; j++) {
            pickup[i][j] = INF;
            for (int k = 0; k < 3; k++) dist[i][j][k] = INF;
        }
    }

    priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq_pickup;

    for (int i = 0; i < N; i++) {
        cin >> players[i].first >> players[i].second;
        pickup[players[i].first][players[i].second] = 0;
        pq_pickup.push({0, {players[i].first, players[i].second}});
    }

    // Dijkstra for pickup costs (Multi-source)
    while (!pq_pickup.empty()) {
        ll d = pq_pickup.top().first;
        int r = pq_pickup.top().second.first;
        int c = pq_pickup.top().second.second;
        pq_pickup.pop();

        if (d > pickup[r][c]) continue;

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (inside(nr, nc)) {
                if (pickup[nr][nc] > d + C) {
                    pickup[nr][nc] = d + C;
                    pq_pickup.push({pickup[nr][nc], {nr, nc}});
                }
            }
        }
    }

    // Main Dijkstra
    // State: 0 = Held, 1 = Vertical, 2 = Horizontal
    priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq;

    int startR = players[0].first;
    int startC = players[0].second;
    int targetR = players[N - 1].first;
    int targetC = players[N - 1].second;

    dist[startR][startC][0] = 0;
    pq.push({0, startR, startC, 0});

    while (!pq.empty()) {
        auto [d, r, c, state] = pq.top();
        pq.pop();

        if (d > dist[r][c][state]) continue;

        // State 0: Held
        if (state == 0) {
            // Kick Vertical
            if (d + B < dist[r][c][1]) {
                dist[r][c][1] = d + B;
                pq.push({dist[r][c][1], r, c, 1});
            }
            // Kick Horizontal
            if (d + B < dist[r][c][2]) {
                dist[r][c][2] = d + B;
                pq.push({dist[r][c][2], r, c, 2});
            }
            // Walk with ball
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (inside(nr, nc)) {
                    if (d + C < dist[nr][nc][0]) {
                        dist[nr][nc][0] = d + C;
                        pq.push({dist[nr][nc][0], nr, nc, 0});
                    }
                }
            }
        }
        // State 1: Flying Vertical
        else if (state == 1) {
            // Land
            if (d + pickup[r][c] < dist[r][c][0]) {
                dist[r][c][0] = d + pickup[r][c];
                pq.push({dist[r][c][0], r, c, 0});
            }
            // Continue Flying Vertical
            for (int i = 2; i < 4; i++) { // South, North
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (inside(nr, nc)) {
                    if (d + A < dist[nr][nc][1]) {
                        dist[nr][nc][1] = d + A;
                        pq.push({dist[nr][nc][1], nr, nc, 1});
                    }
                }
            }
        }
        // State 2: Flying Horizontal
        else if (state == 2) {
            // Land
            if (d + pickup[r][c] < dist[r][c][0]) {
                dist[r][c][0] = d + pickup[r][c];
                pq.push({dist[r][c][0], r, c, 0});
            }
            // Continue Flying Horizontal
            for (int i = 0; i < 2; i++) { // East, West
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (inside(nr, nc)) {
                    if (d + A < dist[nr][nc][2]) {
                        dist[nr][nc][2] = d + A;
                        pq.push({dist[nr][nc][2], nr, nc, 2});
                    }
                }
            }
        }
    }

    cout << dist[targetR][targetC][0] << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...