Submission #1321730

#TimeUsernameProblemLanguageResultExecution timeMemory
1321730norrawichzzzSoccer (JOI17_soccer)C++20
100 / 100
542 ms35656 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>

const int INF = 4e18;

/*
current state of the ball 
/pass
0 = up -> up again , stay
1 = right ...
2 = down...
3 = left...

/move with
4 = the ball is being carried -> move udlr , pass udlr
5 = stay(the ball has been passed and stopped)




*/
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int h,w,a,b,c,n;
    cin>> h>> w>> a>> b>> c>> n;

    vector<pi> pos(n);
    for (int i=0; i<n; i++) cin>> pos[i].first>> pos[i].second;

    // {x, y, state}
    vector<vector<vector<int>>> dp(h+2, vector<vector<int>>(w+2, vector<int>(6, INF)));

    int stx=pos[0].second, sty=pos[0].first;
    int edx=pos[n-1].second, edy=pos[n-1].first;

    dp[sty][stx][4] = 0;
    priority_queue<pair<pi, pi>, vector<pair<pi, pi>>, greater<pair<pi, pi>>> pq;// {cost, state, x, y}
    pq.push({{0, 4}, {sty, stx}});

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

    vector<vector<int>> mndist(h+2, vector<int>(w+2, 0));
    vector<vector<bool>> vst(h+2, vector<bool>(w+2, false));
    queue<pair<int,int>> q;
    for (int i=0; i<n; i++) q.push({pos[i].first, pos[i].second}), vst[pos[i].first][pos[i].second]=true;
    while (!q.empty()) {
        int y=q.front().first, x=q.front().second;
        q.pop();

        for (int e=0; e<4; e++) {
            int nx = x+dx[e], ny = y+dy[e];
            if (nx <= w && nx >= 0 && ny <= h && ny >= 0) {
                if (vst[ny][nx]) continue;
                vst[ny][nx] = true;
                mndist[ny][nx] = mndist[y][x]+1;
                q.push({ny,nx});
            }
        }
    }
    
    while (!pq.empty()) {
        pair<pi,pi> cur = pq.top();
        pq.pop();

        int cost = cur.first.first;
        int state = cur.first.second;
        int y = cur.second.first;
        int x = cur.second.second;

        if (dp[y][x][state] < cost) continue;

        if (state < 4) {
            int nx = x+dx[state], ny = y+dy[state];
            if (nx <= w && nx >= 0 && ny <= h && ny >= 0) {
                if (dp[ny][nx][state] > dp[y][x][state] + a) {
                    dp[ny][nx][state] = dp[y][x][state] + a;
                    pq.push({{dp[ny][nx][state], state}, {ny, nx}});
                }
            }
            if (dp[y][x][5] > dp[y][x][state]) {
                dp[y][x][5] = dp[y][x][state];
                pq.push({{dp[y][x][5], 5}, {y, x}});
            }
        }
        else if (state == 4) {
            
            for (int e=0; e<4; e++) {
                int nx = x+dx[e], ny = y+dy[e];
                if (nx <= w && nx >= 0 && ny <= h && ny >= 0) {
                    if (dp[ny][nx][state] > dp[y][x][state] + c) {
                        dp[ny][nx][state] = dp[y][x][state] + c;
                        pq.push({{dp[ny][nx][state], state}, {ny, nx}});
                    }
                }
            }
            for (int e=0; e<4; e++) {
                int nx = x+dx[e], ny = y+dy[e];
                if (nx <= w && nx >= 0 && ny <= h && ny >= 0) {
                    if (dp[ny][nx][e] > dp[y][x][state] + a + b) {
                        dp[ny][nx][e] = dp[y][x][state] + a + b;
                        pq.push({{dp[ny][nx][e], e}, {ny, nx}});
                    }
                }
            }
        }
        else if (state == 5) {
            if (dp[y][x][4] > dp[y][x][5]+mndist[y][x]*c) {
                dp[y][x][4] = dp[y][x][5]+mndist[y][x]*c;
                pq.push({{dp[y][x][4], 4}, {y, x}});
            }
        }
    }
    cout<< dp[edy][edx][4];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...