제출 #1328918

#제출 시각아이디문제언어결과실행 시간메모리
1328918spetrSoccer (JOI17_soccer)C++20
100 / 100
427 ms29840 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

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

    ll h, w;
    cin >> h >> w;
    h++; w++;

    ll a,b,c;
    cin >> a >> b >> c;

    ll n;
    cin >> n;
    vector<pl> nums;
    for (ll i = 0; i < n; i++){
        ll x,y;
        cin >> x >> y;
        nums.push_back({x,y});
    }

    vll closest (h, vl (w,-1));
    queue<pl> q;
    for (ll i = 0; i < nums.size(); i++){
        ll x,y;
        x = nums[i].first; y = nums[i].second;
        q.push({x,y});
        closest[x][y] = 0;
    }

    vll dirs {{-1,0},{1,0},{0,1},{0,-1}};
    while (!q.empty()){
        auto hrac = q.front(); q.pop();
        ll x,y;
        x = hrac.first; y = hrac.second;
        for (ll j = 0; j < 4; j++){
            ll nx, ny;
            nx = x + dirs[j][0];
            ny = y + dirs[j][1];
            if (0 <= nx && nx < h && 0 <= ny && ny < w){
                if (closest[nx][ny] == -1){
                    closest[nx][ny] = closest[x][y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }

    ll ex, ey;
    ex = nums[n-1].first; ey = nums[n-1].second;
    priority_queue<vl> fronta;
    fronta.push({0, 0, nums[0].first, nums[0].second}); 
    vector<vector<vector<ll>>> dp (5, vll (h, vl(w, 2e18)));
    dp[0][nums[0].first][nums[0].second] = 0;

    while (!fronta.empty()){
        auto prvek = fronta.top();
        fronta.pop();
        ll dis, t, x, y;
        dis = -prvek[0]; t = prvek[1]; x = prvek[2]; y = prvek[3];
        if (x == ex && y == ey && t == 0){
            cout << dis <<"\n";
            return 0;
        }


        if (dis <= dp[t][x][y]){
            if (t == 0){
                for (ll j = 0; j < 4; j++){
                    ll nx = x + dirs[j][0];
                    ll ny = y + dirs[j][1];
                    if (0 <= nx && nx < h && 0 <= ny && ny < w){
                        ll ndis = c + dis;
                        if (ndis < dp[0][nx][ny]){
                            dp[0][nx][ny] = ndis;
                            fronta.push({-ndis, 0, nx, ny});
                        }
                        ndis = a + b + dis;
                        if (ndis < dp[j+1][nx][ny]){
                            dp[j+1][nx][ny] = ndis;
                            fronta.push({-ndis, j+1, nx, ny});
                        }
                    }
                }
            }

            else{
                ll nx = x + dirs[t-1][0];
                ll ny = y + dirs[t-1][1];
                ll ndis = dis + a;
                if (0 <= nx && nx < h && 0 <= ny && ny < w){

                    if (ndis < dp[t][nx][ny]){
                        dp[t][nx][ny] = ndis;
                        fronta.push({-ndis, t, nx, ny});
                    }
                }
                ndis = dis + closest[x][y]*c;
                if (ndis < dp[0][x][y]){
                    dp[0][x][y] = ndis;
                    fronta.push({-ndis, 0, x, y});
                }
            
            }
        }
    }





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