제출 #1144065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144065		alir3za_zar3	Soccer (JOI17_soccer)	C++20	100 / 100	1244 ms	51376 KiB

soccer

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long
#define     toP     tuple<int,int,int,int>

const int N=5e2+7 , K=7;
const int M=1e5+7 , Inf=2e18;
int H,W , A,B,C , n , S[M],T[M] , ln[N][N];
int preX[4]={0,0,1,-1} , preY[4]={1,-1,0,0};
int dp[N][N][K];
bool vis[N][N][K] , mrk[N][N];
queue<pair<int,int>> q;
priority_queue<toP,vector<toP>,greater<toP>> pq;

void iN ()
{
    cin >> H >> W; H++; W++;
    cin >> A >> B >> C >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> S[i] >> T[i];
        S[i]++;      T[i]++;
        q.push({S[i],T[i]});
        mrk[S[i]][T[i]] = 1;
    }
    for (int i=0; i<=max(H,W)+1; i++)
    {
        mrk[0][i]=mrk[H+1][i]=mrk[i][0]=mrk[i][W+1]=true;
        for (int k=0; k<K; k++)
            vis[0][i][k]=vis[H+1][i][k]=vis[i][0][k]=vis[i][W+1][k]=true;
    }
    for (int i=1; i<=H; i++)
        for (int j=1; j<=W; j++)
            for (int k=0; k<K; k++)
                dp[i][j][k] = Inf;       
}

void enginE ()
{
    while (!q.empty())
    {
        auto [a,b] = q.front();
        q.pop();
        for (int k=0; k<4; k++)
        {
            int x=preX[k]+a , y=preY[k]+b;
            if (!mrk[x][y])
            {
                mrk[x][y] = true;
                ln[x][y] = ln[a][b]+1;
                q.push({x,y});
            }
        }
    }

    pq.push({0,4,S[1],T[1]});
    while (!pq.empty())
    {
        auto [o,typ,s,t] = pq.top();
        pq.pop();
        if (vis[s][t][typ]) continue;
        dp[s][t][typ] = o;
        vis[s][t][typ] = true;
        int x,y;
        if (typ < 4)
        {
            x=s+preX[typ] , y=t+preY[typ];
            pq.push({A+o , typ , x , y});
            pq.push({B+o , 5 , s , t});
        }
        if (typ == 5)
            pq.push({o+C*ln[s][t] , 4 , s , t});
        for (int k=0; k<4; k++)
        {
            x=s+preX[k] , y=t+preY[k];
            if (typ == 4)
            {
                pq.push({o+A , k , x , y});
                pq.push({o+C , 4 , x , y});
            }
        }
    }
}

void ouT ()
{
    cout << dp[S[n]][T[n]][4] << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    iN();
    enginE();
    ouT();
}

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