Submission #1324227

#TimeUsernameProblemLanguageResultExecution timeMemory
1324227mantaggezSoccer (JOI17_soccer)C++20
0 / 100
395 ms23672 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using tup = tuple<ll, ll, ll, ll>;

const int hx = 505;
const int nx = 1e5+5;
const ll INF = 1e18;

int h, w, a, b, c, n;
int s[nx], t[nx], vs[hx][hx], di[] = {-1, 0, 0, 1}, dj[] = {0, -1, 1, 0};
ll dist[hx][hx], dp[hx][hx][6];
queue<pii> q;
priority_queue<tup, vector<tup>, greater<tup>> pq; // fatigue, i, j, state

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> h >> w >> a >> b >> c >> n;
    for(int i=0;i<=h;i++)
        for(int j=0;j<=w;j++)
            for(int k=0;k<6;k++)
                dp[i][j][k] = INF;
    for(int i=0;i<=h;i++)
        for(int j=0;j<=w;j++)
            dist[i][j] = INF;
    for(int i=1;i<=n;i++) cin >> s[i] >> t[i], q.push({s[i], t[i]}), dist[s[i]][t[i]] = 0;

    while(!q.empty())
    {
        auto [ci, cj] = q.front();
        q.pop();
        if(vs[ci][cj]) continue;
        vs[ci][cj] = 1;
        for(int d=0;d<4;d++)
        {
            ll ni = ci + di[d], nj = cj + dj[d];
            if(0 <= ni && ni <= h && 0 <= nj && nj <= w && dist[ni][nj] > dist[ci][cj] + 1)
            {
                dist[ni][nj] = dist[ci][cj] + 1;
                q.push({ni, nj});
            }
        }
    }
        
    // 0-3 = ball moving, 4 = still, 5 = dribbling;
    dp[s[1]][t[1]][5] = 0;
    pq.push({0, s[1], t[1], 5});
    while(!pq.empty())
    {
        auto [cw, ci, cj, state] = pq.top();
        pq.pop();
        // cout << ci << ' ' << cj << ' ' << state << " : " << cw << '\n';
        if(state < 4)
        {
            ll ni = ci + di[state], nj = cj + dj[state];
            if(0 <= ni && ni <= h && 0 <= nj && nj <= w) {
                if(dp[ci][cj][state] + a < dp[ni][nj][state]) {
                    dp[ni][nj][state] = dp[ci][cj][state] + a;
                    pq.push({dp[ni][nj][state], ni, nj, state});
                }
            }
            
            if(dp[ci][cj][state] < dp[ci][cj][4]) {
                dp[ci][cj][4] = dp[ci][cj][state];
                pq.push({dp[ci][cj][4], ci, cj, 4});
            }
        }

        else if(state == 4)
        {
            if(dist[ci][cj] * c + dp[ci][cj][state] < dp[ci][cj][5]) {
                // cout << "dist : " << dist[ci][cj] << '\n';
                dp[ci][cj][5] = dist[ci][cj] * c + dp[ci][cj][state];
                pq.push({dp[ci][cj][5], ci, cj, 5}); 
            }
        }

        else if(state == 5)
        {
            for(int d=0;d<4;d++)
            {
                int ni = ci + di[d], nj = cj + dj[d];
                if(0 <= ni && ni <= h && 0 <= nj && nj <= w) {
                    if(dp[ci][cj][state] + b + a < dp[ni][nj][d]) {
                        dp[ni][nj][d] = dp[ci][cj][state] + b + a;
                        pq.push({dp[ni][nj][d], ni, nj, d});
                    }

                    if(dp[ci][cj][state] + c < dp[ni][nj][state]) {
                        dp[ni][nj][state] = dp[ci][cj][state] + c;
                        pq.push({dp[ni][nj][state], ni, nj, state});
                    }
                }
            }
        }
    }

    // for(int i=0;i<=h;i++) {
    //     for(int j=0;j<=w;j++) {
    //         for(int k=0;k<6;k++) {
    //             cout << "dp[" << i << "][" << j << "][" << k << "] : " << dp[i][j][k] << '\n'; 
    //         }
    //     }
    // }

    cout << dp[h][w][5];

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...