제출 #1290529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290529		Gray	Soccer (JOI17_soccer)	C++20	30 / 100	3098 ms	142688 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;
pair<ll, ll> a[N+1];
pair<ll, ll> dist[H+1][W+1];
pair<ll, ll> 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].ff >> a[i].ss;

    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].ff, j=a[ind].ss;
        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].ff==-1){
                    dist[ni][nj].ff=id;
                    que1.push({id, ni, nj});
                }else if (dist[ni][nj].ss==-1 and dist[ni][nj].ss!=id){
                    dist[ni][nj].ss=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<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> que;
    que.push({0, a[0].ff, a[0].ss, 0});
    dp[a[0].ff][a[0].ss].ff = 0;
    while (!que.empty()){
        auto cur = que.top(); que.pop();
        ll i, j, cost, usd; tie(cost, i, j, usd)=cur;
        if (vis[i][j][usd]) continue;
        vis[i][j][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].ff){
                if (dp[ni][nj].ff>cost+C*(abs(i-ni)+abs(j-nj))){
                    dp[ni][nj].ff=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].ss;
                if (dp[ni][nj].ss>cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj].ss=cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj].ss, ni, nj, 1});
                }
            }else{
                ll susd = dist[ni][nj].ff;
                if (dp[ni][nj].ff>cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj].ff=cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj].ff, ni, nj, 0});
                }
            }
        }
        for (ll nj = 0; nj<=w; nj++){
            if (j==nj) continue;
            ll ni = i;
            if (usd==dist[ni][nj].ff){
                if (dp[ni][nj].ff>cost+C*(abs(i-ni)+abs(j-nj))){
                    dp[ni][nj].ff=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].ss;
                if (dp[ni][nj].ss>cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj].ss=cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj].ss, ni, nj, 1});
                }
            }else{
                ll susd = dist[ni][nj].ff;
                if (dp[ni][nj].ff>cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B){
                    dp[ni][nj].ff=cost+C*(abs(a[susd].ff-ni)+abs(a[susd].ss-nj))+(abs(i-ni)+abs(j-nj))*A+B;
                    que.push({dp[ni][nj].ff, 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].ff==n-1){
                res=min(res, dp[i][j].ff);
            }else if (dist[i][j].ss==n-1){
                res=min(res, dp[i][j].ss);
            }
            ll mn = min(dp[i][j].ff, dp[i][j].ss);
            res=min(res, mn+C*(abs(i-a[n-1].ff)+abs(j-a[n-1].ss)));
        }
    }
    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