Submission #1278823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278823		MisterReaper	Soccer (JOI17_soccer)	C++20	35 / 100	26 ms	2500 KiB

soccer

// File soccer.cpp created on 13.10.2025 at 15:04:15
#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;
}

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

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

    i64 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];
    }

    std::vector<i64> dis(N, inf);
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> pq;
    pq.emplace(dis[0] = 0, 0);
    while (!pq.empty()) {
        auto[d, i] = pq.top();
        pq.pop();
        if (dis[i] != d) {
            continue;
        }
        for (int j = 0; j < N; ++j) {
            int dx = std::abs(S[i][0] - S[j][0]);
            int dy = std::abs(S[i][1] - S[j][1]);
            if (chmin(dis[j], d + A * dx + B + C * dy)) {
                pq.emplace(dis[j], j);
            }
            if (chmin(dis[j], d + A * dy + B + C * dx)) {
                pq.emplace(dis[j], j);
            }
            if (chmin(dis[j], d + C * dx + C * dy)) {
                pq.emplace(dis[j], j);
            }
        }
    }

    std::cout << dis[N - 1] << '\n';

    return 0;
}

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