Submission #1321693

#TimeUsernameProblemLanguageResultExecution timeMemory
1321693kantaponzSoccer (JOI17_soccer)C++20
5 / 100
407 ms32492 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll dist[505][505], dp[505][505][6], vis[505][505][6];
int H, W, N, px[505], py[505];
ll A, B, C;
queue<pair<int,int>> q;
priority_queue<tuple<ll,int,int,int>, vector<tuple<ll,int,int,int>>, greater<tuple<ll,int,int,int>>> pq;
int xx[] = {0, -1, 0, 1};
int yy[] = {1, 0, -1, 0};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> H >> W >> A >> B >> C >> N;
    H++, W++;

    for (int i = 0; i < 505; i++) for (int j = 0; j < 505; j++) dist[i][j] = 1e18;
    for (int i = 0; i < 505; i++) for (int j = 0; j < 505; j++) for (int k = 0; k < 6; k++) dp[i][j][k] = 1e18;

    for (int i = 1; i <= N; i++) {
        cin >> py[i] >> px[i];
        px[i]++, py[i]++;
        q.emplace(py[i], px[i]);
        dist[py[i]][px[i]] = 0;
    }
    
    
    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + yy[i], nx = x + xx[i];
            if (ny < 1 || ny > H || nx < 1 || nx > W) continue;
            if (dist[ny][nx] <= dist[y][x] + C) continue;
            dist[ny][nx] = dist[y][x] + C;
            q.emplace(ny, nx);
        }
    }

    dp[py[1]][px[1]][4] = 0;
    pq.emplace(0, py[1], px[1], 4);
    while (!pq.empty()) {
        auto [w, y, x, st] = pq.top();
        pq.pop();
        //cout << w << " " << y << " " << x << " " << st << endl;
        if (vis[y][x][st]) continue;
        vis[y][x][st] = 1;

        if (st < 4) {
            if (dp[y][x][4] > w) {
                dp[y][x][4] = w;
                pq.emplace(w, y, x, 4);
            }
            int ny = y + yy[st], nx = x + xx[st];
            if (ny >= 1 && ny <= H && nx >= 1 && nx <= W && dp[ny][nx][st] > w + A) {
                dp[ny][nx][st] = w + A;
                pq.emplace(w + A, ny, nx, st);
            }
        }

        if (st == 4) {
            if (dp[y][x][5] > w + dist[y][x]) {
                dp[y][x][5] = w + dist[y][x];
                pq.emplace(dp[y][x][5], y, x, 5);
            }
        }

        if (st == 5) {

            for (int i = 0; i < 4; i++) {
                int ny = y + yy[i], nx = x + xx[i];
                if (ny < 1 || ny > H || nx < 1 || nx > W) continue;
                if (dp[ny][nx][i] <= w + A + B) continue;
                dp[ny][nx][i] = w + A + B;
                pq.emplace(dp[ny][nx][i], ny, nx, i);
                
            }

            for (int i = 0; i < 4; i++) {
                int ny = y + yy[i], nx = x + xx[i];
                if (ny < 1 || ny > H || nx < 1 || nx > W) continue;
                if (dp[ny][nx][5] <= w + C) continue;
                dp[ny][nx][5] = w + C;
                pq.emplace(dp[ny][nx][5], ny, nx, 5);
                
            }
        }
    }

    cout << min(dp[py[N]][px[N]][4], dp[py[N]][px[N]][5]);

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...