Submission #1160856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160856		12345678	Soccer (JOI17_soccer)	C++20	100 / 100	448 ms	36532 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=1e5+5, mx=5e2+5, inf=1e18;

ll n, a, b, c, dp[mx][mx][6], vs[mx][mx][6], h, w, s[nx], t[nx], dist[mx][mx], di[4]={1, 0, 0, -1}, dj[4]={0, 1, -1, 0};
queue<pair<ll, ll>> q;
priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    h++, w++;
    cin>>a>>b>>c;
    cin>>n;
    for (int i=1; i<=h; i++) for (int j=1; j<=w ;j++) dist[i][j]=inf;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) for (int k=0; k<6; k++) dp[i][j][k]=inf;
    for (int i=1; i<=n; i++) cin>>s[i]>>t[i], 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();
        for (int i=0; i<4; i++)
        {
            int ni=ci+di[i], nj=cj+dj[i];
            if (ni>=1&&ni<=h&&nj>=1&&nj<=w&&dist[ni][nj]>dist[ci][cj]+1)
            {
                dist[ni][nj]=dist[ci][cj]+1;
                q.push({ni, nj});
            } 
        }
    }
    /*
    for (int i=1; i<=h; i++)
    {
        for (int j=1; j<=w; j++) cout<<dist[i][j]<<' ';
        cout<<'\n';
    }
    */
    dp[s[1]][t[1]][4]=0;
    pq.push({0, s[1], t[1], 4});
    while (!pq.empty())
    {
        auto [cw, ci, cj, idx]=pq.top();
        pq.pop();
        if (vs[ci][cj][idx]) continue;
        vs[ci][cj][idx]=1;
        //cout<<"dijkstra "<<cw<<' '<<ci<<' '<<cj<<' '<<idx<<'\n';
        if (idx<4)
        {
            if (cw<dp[ci][cj][4])
            {
                dp[ci][cj][4]=cw;
                pq.push({dp[ci][cj][4], ci, cj, 4});
            }
            int ni=ci+di[idx], nj=cj+dj[idx];
            if (1<=ni&&ni<=h&&1<=nj&&nj<=w&&dp[ni][nj][idx]>cw+a)
            {
                dp[ni][nj][idx]=cw+a;
                pq.push({dp[ni][nj][idx], ni, nj, idx});
            }
        }
        if (idx==4)
        {
            if (dist[ci][cj]*c+cw<dp[ci][cj][5])
            {
                dp[ci][cj][5]=dist[ci][cj]*c+cw;
                pq.push({dp[ci][cj][5], ci, cj, 5});
            }
        }
        if (idx==5)
        {
            for (int i=0; i<4; i++)
            {
                int ni=ci+di[i], nj=cj+dj[i];
                if (1<=ni&&ni<=h&&1<=nj&&nj<=w&&cw+a+b<dp[ni][nj][i])
                {
                    dp[ni][nj][i]=cw+a+b;
                    pq.push({dp[ni][nj][i], ni, nj, i});
                }
                if (1<=ni&&ni<=h&&1<=nj&&nj<=w&&cw+c<dp[ni][nj][5])
                {
                    dp[ni][nj][5]=cw+c;
                    pq.push({dp[ni][nj][5], ni, nj, 5});
                }
            }
        }
    }
    cout<<dp[s[n]][t[n]][5];
}

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