Submission #595340

#	Time	Username	Problem	Language	Result	Execution time	Memory
595340		piOOE	Soccer (JOI17_soccer)	C++17	100 / 100	847 ms	203800 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2001;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

ll dp[5][N][N], mind[N][N];

const int dx[5] = {-1, 1, 0, -1, 0};
const int dy[5] = {-1, 0, -1, 0, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp, 63, sizeof(dp)), memset(mind, 63, sizeof(mind));
    ll a, b, c;
    int h, w, n;
    cin >> h >> w >> a >> b >> c >> n;
    vector<int> x(n), y(n);
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        q.push({x[i], y[i]});
        mind[x[i]][y[i]] = 0;
    }
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 1; k <= 4; ++k) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && ni <= h && nj >= 0 && nj <= w && mind[ni][nj] == inf) {
                mind[ni][nj] = mind[i][j] + c;
                q.push({ni, nj});
            }
        }
    }
    set<tuple<ll, int, int, int>> st;
    auto relax = [&st](ll dist, int tp, int x, int y) {
        if (dp[tp][x][y] > dist) {
            st.erase({dp[tp][x][y], tp, x, y});
            dp[tp][x][y] = dist;
            st.insert({dp[tp][x][y], tp, x, y});
        }
    };
    relax(0, 0, x[0], y[0]);
    while (!st.empty()) {
        auto [d, t, i, j] = *st.begin();
        st.erase(st.begin());
        if (t == 0) {
            for (int k = 1; k <= 4; ++k) {
                int ni = i + dx[k], nj = j + dy[k];
                if (ni >= 0 && ni <= h && nj >= 0 && nj <= w) {
                    relax(d + a + b, k, ni, nj);
                    relax(d + c, 0, ni, nj);
                }
            }
        } else {
            relax(d + mind[i][j], 0, i, j);
            int ni = i + dx[t], nj = j + dy[t];
            if (ni >= 0 && ni <= h && nj >= 0 && nj <= w) {
                relax(d + a, t, ni, nj);
            }
        }
    }
    cout << dp[0][x[n - 1]][y[n - 1]];
    return 0;
}

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