Submission #1278842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278842		MisterReaper	Soccer (JOI17_soccer)	C++20	0 / 100	812 ms	327680 KiB

soccer

// File soccer.cpp created on 13.10.2025 at 15:43:22
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int dx[] = {0, -1, 0, +1};
constexpr int dy[] = {-1, 0, +1, 0};

template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int H, W;
    std::cin >> H >> W;

    H++;
    W++;

    int A, B, C;
    std::cin >> A >> B >> C;

    int N;
    std::cin >> N;

    std::vector<std::array<int, 2>> S(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> S[i][0] >> S[i][1];
    }

    auto in = [&](int x, int y) -> bool {
        return 0 <= x && x < H && 0 <= y && y < W;
    };

    std::queue<std::pair<int, int>> que;
    std::vector<std::vector<int>> dis(H, std::vector<int>(W, -1));
    for (int i = 0; i < N; ++i) {
        dis[S[i][0]][S[i][1]] = 0;
        que.emplace(S[i][0], S[i][1]);
    }

    while (!que.empty()) {
        auto[x, y] = que.front();
        que.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (in(nx, ny) && dis[nx][ny] == -1) {
                dis[nx][ny] = dis[x][y] + 1;
                que.emplace(nx, ny);
            }
        }
    }

    auto code = [&](int i, int j, int tp) -> int {
        return tp * H * W + i * W + j;
    };
    auto decode = [&](int x) -> std::array<int, 3> {
        int tp = x / (H * W);
        x -= tp * H * W;
        int i = x / W;
        int j = x % W;
        return {tp, i, j};
    };

    std::vector<std::vector<std::pair<int, i64>>> adj(5 * H * W);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            for (int d = 0; d < 4; ++d) {
                int ni = i + dx[d];
                int nj = j + dy[d];
                adj[code(i, j, 0)].emplace_back(code(i, j, d + 1), B);
                adj[code(i, j, d + 1)].emplace_back(code(i, j, 0), C * dis[i][j]);
                if (in(ni, nj)) {
                    adj[code(i, j, 0)].emplace_back(code(ni, nj, 0), C);
                    adj[code(i, j, d + 1)].emplace_back(code(ni, nj, d + 1), A);
                }
            }
        }
    }

    std::vector<i64> mind(5 * H * W, inf);
    min_pq<std::pair<i64, int>> pq;
    pq.emplace(mind[code(S[0][0], S[0][1], 0)] = 0, code(S[0][0], S[0][1], 0));
    while (!pq.empty()) {
        auto[d, v] = pq.top();
        pq.pop();
        if (mind[v] != d) {
            continue;
        }
        for (auto[u, c] : adj[v]) {
            if (chmin(mind[u], mind[v] + c)) {
                pq.emplace(mind[u], u);
            }
        }
    }

    i64 ans = mind[code(S[N - 1][0], S[N - 1][1], 0)];

    std::cout << ans << '\n';

    return 0;
}

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