제출 #1323410

#제출 시각아이디문제언어결과실행 시간메모리
1323410chithanhnguyenSoccer (JOI17_soccer)C++20
100 / 100
321 ms22540 KiB
/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

struct DijkstraState {
    int cost, x, y, d;

    bool operator > (const DijkstraState &other) const {
        return cost > other.cost;
    }
};

const int MAXN = 1e5 + 5;
const int MAXH = 505;
const int INF  = 1e18 + 5;
int h, w, a, b, c, n;
pii balls[MAXN];

void init() {
    cin >> h >> w >> a >> b >> c >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        balls[i] = {x, y};
    }
}

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
int cost[MAXH][MAXH];
int dist[MAXH][MAXH][5];

bool inside(int x, int y) {
    bool cond1 = (0 <= x && x <= h);
    bool cond2 = (0 <= y && y <= w);
    return (cond1 && cond2);
}

void prepare_cost() {
    for (int i = 0; i <= h; ++i)
        for (int j = 0; j <= w; ++j)
            cost[i][j] = INF;

    queue<pii> bfsQueue;
    for (int i = 1; i <= n; ++i) {
        int x = balls[i].fi, y = balls[i].se;
        cost[x][y] = 0;
        bfsQueue.push({x, y});
    }

    while (!bfsQueue.empty()) {
        pii cur = bfsQueue.front();
        int x = cur.fi, y = cur.se;
        bfsQueue.pop();

        for (int nxt_dir = 0; nxt_dir < 4; ++nxt_dir) {
            int nx = x + dx[nxt_dir];
            int ny = y + dy[nxt_dir];

            if (!inside(nx, ny)) continue;

            int newcost = cost[x][y] + 1;
            if (cost[nx][ny] > newcost) {
                cost[nx][ny] = newcost;
                bfsQueue.push({nx, ny});
            }
        }
    }
}

void dijkstra() {
    for (int i = 0; i <= h; ++i)
        for (int j = 0; j <= w; ++j)
            for (int d = 0; d <= 4; ++d)
                dist[i][j][d] = INF;

    priority_queue<DijkstraState, vector<DijkstraState>, greater<DijkstraState>> pq;
    int start_x = balls[1].fi, start_y = balls[1].se;
    pq.push({0, start_x, start_y, 4});
    dist[start_x][start_y][4] = 0;

    auto relaxState = [&] (int x, int y, int d, int newcost) {
        if (dist[x][y][d] > newcost) {
            dist[x][y][d] = newcost;
            pq.push({newcost, x, y, d});
        }
    };

    while (!pq.empty()) {
        int cur_cost = pq.top().cost;
        int x = pq.top().x, y = pq.top().y, d = pq.top().d;
        pq.pop();

        if (dist[x][y][d] < cur_cost) continue;

        // Bóng đang cố định
        if (d == 4) {
            // Đá bóng đi
            for (int nxtd = 0; nxtd < 4; ++nxtd)
                relaxState(x, y, nxtd, cur_cost + b);
            
            // Di chuyển bóng đi
            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (inside(nx, ny))
                    relaxState(nx, ny, 4, cur_cost + c);
            }
        } 
        // Bóng đang trong tình trạng bị đá
        else {
            // Bóng tiếp tục di chuyển
            {
                int nx = x + dx[d], ny = y + dy[d];
                if (inside(nx, ny))
                    relaxState(nx, ny, d, cur_cost + a);
            }

            // Có người đến nhặt bóng
            relaxState(x, y, 4, cur_cost + cost[x][y] * c);
        }
    }
}

void solve() {
    prepare_cost();
    dijkstra();

    cout << dist[balls[n].fi][balls[n].se][4];
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    solve();

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