Submission #520016

#	Time	Username	Problem	Language	Result	Execution time	Memory
520016		Giantpizzahead	Soccer (JOI17_soccer)	C++17	100 / 100	415 ms	18596 KiB

soccer

/*
Solution: 
Runtime: 
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;

const int MAXD = 505;
const ll INF = 1e18;

int H, W, N;
int si, sj, ei, ej;
ll A, B, C;
ll costP[MAXD][MAXD];

int ci[] = {1, 0, -1, 0}, cj[] = {0, 1, 0, -1};

inline bool inBounds(int i, int j) {
    return i >= 0 && i < H && j >= 0 && j < W;
}

// 0-3 = Being kicked, 4 = Player has the ball
ll bestC[MAXD][MAXD][5];
struct Loc {
    int i, j, k;
    ll c;
    bool operator<(const Loc& o) const {
        return c > o.c;
    }
};
priority_queue<Loc> pq;

void tryTrans(int i, int j, int k, ll c) {
    if (!inBounds(i, j) || bestC[i][j][k] <= c) return;
    bestC[i][j][k] = c;
    pq.push({i, j, k, c});
}

void bfs1() {
    while (!pq.empty()) {
        Loc l = pq.top(); pq.pop();
        int i = l.i, j = l.j;
        ll c = l.c;
        if (c != costP[i][j]) continue;
        // Move to adjacent square
        rep(d, 0, 4) {
            int ni = i + ci[d], nj = j + cj[d];
            ll nc = c + C;
            if (!inBounds(ni, nj) || costP[ni][nj] <= nc) continue;
            costP[ni][nj] = nc;
            pq.push({ni, nj, -1, nc});
        }
    }
}

void bfs2() {
    bestC[si][sj][4] = 0;
    pq.push({si, sj, 4, 0});
    while (!pq.empty()) {
        Loc l = pq.top(); pq.pop();
        int i = l.i, j = l.j, k = l.k;
        ll c = l.c;
        if (c != bestC[i][j][k]) continue;
        if (k == 4) {
            // Player has the ball
            rep(d, 0, 4) {
                tryTrans(i + ci[d], j + cj[d], 4, c + C);  // Move with the ball
                tryTrans(i, j, d, c + B);  // Kick the ball in a direction
            }
        } else {
            // Ball is being kicked
            // Continue moving the ball
            tryTrans(i + ci[k], j + cj[k], k, c + A);
            // Stop moving and have a player pick up the ball
            tryTrans(i, j, 4, c + costP[i][j]);
        }
    }
}

void solve() {
    cin >> H >> W;
    H++, W++;
    cin >> A >> B >> C;
    cin >> N;
    rep(i, 0, H) rep(j, 0, W) {
        costP[i][j] = INF;
        rep(k, 0, 5) bestC[i][j][k] = INF;
    }
    rep(k, 0, N) {
        int i, j; cin >> i >> j;
        if (k == 0) si = i, sj = j;
        else if (k == N-1) ei = i, ej = j;
        costP[i][j] = 0;
        pq.push({i, j, -1, 0});
    }
    bfs1();
    bfs2();
    ll ans = INF;
    rep(i, 0, H) rep(j, 0, W) rep(k, 0, 5) {
        ll cost = bestC[i][j][k] + C * (abs(ei-i) + abs(ej-j));
        ans = min(cost, ans);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65