제출 #1290522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290522		Gray	Soccer (JOI17_soccer)	C++20	30 / 100	3099 ms	75824 KiB

soccer

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e18;
const ll MOD = 1000000007;
const ll N = 2e5;
const ll W = 500, H=500;
array<ll, 2> a[N+1];
array<ll, 2> dist[H+1][W+1];
array<ll, 2> dp[H+1][W+1];
array<ll, 2> vis[H+1][W+1];
vector<pair<ll, ll>> mvs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};


void solve(){
    ll h, w, A, B, C; 
    cin >> h >> w >> A >> B >> C;
    ll n; cin >> n;
    for (ll i=0; i<n; i++) cin >> a[i][0] >> a[i][1];

    for (ll i=0; i<=h; i++) for (ll j=0; j<=w; j++) {
        dist[i][j] = {-1, -1};
        dp[i][j] = {INF, INF};
    }


    queue<array<ll, 3>> que1;
    for (ll ind=0; ind<n; ind++) {
        ll i=a[ind][0], j=a[ind][1];
        dist[i][j]={ind, -1};
        que1.push({ind, i, j});
    }
    while (!que1.empty()){
        ll id, i, j; 
        id=que1.front()[0]; 
        i = que1.front()[1];
        j = que1.front()[2];
        que1.pop();
        for (auto [di, dj]:mvs){
            ll ni = i+di, nj=j+dj;
            if (ni>=0 and ni<=h and nj>=0 and nj<=w){
                if (dist[ni][nj][0]==-1){
                    dist[ni][nj][0]=id;
                    que1.push({id, ni, nj});
                }else if (dist[ni][nj][1]==-1 and dist[ni][nj][0]!=id){
                    dist[ni][nj][1]=id;
                    que1.push({id, ni, nj});
                }
            }
        }
    }
    // for (ll i=0; i<=h; i++){
    //     for (ll j=0; j<=w; j++) cout << dist[i][j][0] << ' ';
    //     cout << ln;
    // }
    // return;
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> que;
    que.push({0, a[0][0], a[0][1], 0});
    dp[a[0][0]][a[0][1]][0] = 0;
    while (!que.empty()){
        auto cur = que.top(); que.pop();
        ll i = cur[1], j=cur[2], cost = cur[0], usd=cur[3];
        if (vis[cur[1]][cur[2]][usd]) continue;
        vis[cur[1]][cur[2]][usd]=1;
        // cout << i << " " << j << ": " << cost << " through " << usd << ln;
        for (ll ni = 0; ni<=h; ni++){
            if (i==ni) continue;
            ll nj = j;
            if (usd==dist[ni][nj][0]){
                if (dp[ni][nj][0]>cost+C*(abs(i-ni)+abs(j-nj))){
                    dp[ni][nj][0]=cost+C*(abs(i-ni)+abs(j-nj)); 
                    que.push({cost+C*(abs(i-ni)+abs(j-nj)), ni, nj, 0});
                }
                ll susd = dist[ni][nj][1];
                if (dp[ni][nj][1]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][1]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][1], ni, nj, 1});
                }
            }else{
                ll susd = dist[ni][nj][0];
                if (dp[ni][nj][0]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][0]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][0], ni, nj, 0});
                }
            }
        }
        for (ll nj = 0; nj<=w; nj++){
            if (j==nj) continue;
            ll ni = i;
            if (usd==dist[ni][nj][0]){
                if (dp[ni][nj][0]>cost+C*(abs(i-ni)+abs(j-nj))){
                    dp[ni][nj][0]=cost+C*(abs(i-ni)+abs(j-nj)); 
                    que.push({cost+C*(abs(i-ni)+abs(j-nj)), ni, nj, 0});
                }
                ll susd = dist[ni][nj][1];
                if (dp[ni][nj][1]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][1]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][1], ni, nj, 1});
                }
            }else{
                ll susd = dist[ni][nj][0];
                if (dp[ni][nj][0]>cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj][0]=cost+C*(abs(a[susd][0]-ni)+abs(a[susd][1]-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj][0], ni, nj, 0});
                }
            }
        }
    }
    ll res=INF;
    // for (ll i=0; i<=h; i++){
    //     for (ll j=0; j<=w; j++){
    //         ll mn = INF;
    //         for (auto [x, y]:dp[i][j]) mn=min(mn, y);
    //         cout << mn << " ";
    //     }
    //     cout << ln;
    // }
    for (ll i=0; i<=h; i++){
        for (ll j=0; j<=w; j++){
            if (dist[i][j][0]==n-1){
                res=min(res, dp[i][j][0]);
            }else if (dist[i][j][1]==n-1){
                res=min(res, dp[i][j][1]);
            }
            ll mn = min(dp[i][j][0], dp[i][j][1]);
            res=min(res, mn+C*(abs(i-a[n-1][0])+abs(j-a[n-1][1])));
        }
    }
    cout << res << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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