Submission #1144045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144045		alir3za_zar3	Soccer (JOI17_soccer)	C++20	0 / 100	3096 ms	49472 KiB

soccer

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

const int N=5e2+7 , K=5;
const int    Inf = 2e18;
int H,W , A,B,C , n , S,T;
int dp[N][N][K];

void iN ()
{
    cin >> H >> W;
    for (int i=0; i<=H; i++)
        for (int j=0; j<=W; j++)
            fill_n(dp[i][j],K,Inf);
    cin >> A >> B >> C >> n;
    cin >> S >> T;
    dp[S][T][0]=dp[S][T][1]=dp[S][T][2]=0;
    for (int i=2; i<n; i++)
    {
        int s,t; cin >> s >> t;
        dp[s][t][0] = 0;
    }
    cin >> S >> T;
}

void Dijkstra ()
{
    set<tuple<int,int,int,int>> q;
    for (int i=0; i<=H; i++)
        for (int j=0; j<=W; j++)
        {
            q.insert({dp[i][j][2],i,j,2});
            q.insert({dp[i][j][0],i,j,0});
        }

    while (!q.empty())
    {
        auto [o,i,j,typ] = *q.begin();
        q.erase(q.begin());

        if (typ == 0)
        {
            for (int I=0; I<=H; I++)
            {
                if (I == i) continue;
                bool flg0 , flg2; flg0=flg2=0;
                if (q.count({dp[I][j][0],I,j,0}))
                {
                    q.erase({dp[I][j][0],I,j,0});
                    flg0 = true;
                }
                if (q.count({dp[I][j][2],I,j,2}))
                {
                    q.erase({dp[I][j][2],I,j,2});
                    flg2 = true;
                }

                if (dp[I][j][0] > o+C*abs(I-i))
                    dp[I][j][0] = o+C*abs(I-i);

                int update = min(dp[I][j][2],
                                dp[I][j][0]+dp[I][j][1]);
                if (dp[I][j][2] > update)
                    dp[I][j][2] = update;
                
                if (flg0) q.insert({dp[I][j][2],I,j,0});
                if (flg2) q.insert({dp[I][j][2],I,j,2});
            }
            for (int J=0; J<=W; J++)
            {
                if (J == j) continue;
                bool flg0 , flg2; flg0=flg2=0;
                if (q.count({dp[i][J][0],i,J,0}))
                {
                    q.erase({dp[i][J][0],i,J,0});
                    flg0 = true;
                }
                if (q.count({dp[i][J][2],i,J,2}))
                {
                    q.erase({dp[i][J][2],i,J,2});
                    flg2 = true;
                }
                if (dp[i][J][0] > o+C*abs(J-j))
                    dp[i][J][0] = o+C*abs(J-j);

                int update = min(dp[i][J][2],
                                dp[i][J][0]+dp[i][J][1]);
                if (dp[i][J][2] > update)
                    dp[i][J][2] = update;
                
                if (flg0) q.insert({dp[i][J][2],i,J,0});
                if (flg2) q.insert({dp[i][J][2],i,J,2});
            }
            continue;
        }
        for (int I=0; I<=H; I++)
        {
            if (I == i) continue;
            bool flg0 , flg2; flg0=flg2=0;
            if (q.count({dp[I][j][0],I,j,0}))
            {
                q.erase({dp[I][j][0],I,j,0});
                flg0 = true;
            }
            if (q.count({dp[I][j][2],I,j,2}))
            {
                q.erase({dp[I][j][2],I,j,2});
                flg2 = true;
            }

            if (dp[I][j][0] > o+C*abs(I-i))
                dp[I][j][0] = o+C*abs(I-i);

            if (dp[I][j][1] > o+A*abs(I-i)+B)
                dp[I][j][1] = o+A*abs(I-i)+B;

            if (dp[I][j][1] > o+C*abs(I-i))
                dp[I][j][1] = o+C*abs(I-i);
            
            int update = min(o+C*abs(I-i),
                            dp[I][j][0]+dp[I][j][1]);
            if (dp[I][j][2] > update)
                dp[I][j][2] = update;
            
            if (flg0) q.insert({dp[I][j][2],I,j,0});
            if (flg2) q.insert({dp[I][j][2],I,j,2});
        }
        for (int J=0; J<=W; J++)
        {
            if (J == j) continue;
            bool flg0 , flg2; flg0=flg2=0;
            if (q.count({dp[i][J][0],i,J,0}))
            {
                q.erase({dp[i][J][0],i,J,0});
                flg0 = true;
            }
            if (q.count({dp[i][J][2],i,J,2}))
            {
                q.erase({dp[i][J][2],i,J,2});
                flg2 = true;
            }
            if (dp[i][J][0] > o+C*abs(J-j))
                dp[i][J][0] = o+C*abs(J-j);

            if (dp[i][J][1] > o+A*abs(J-j)+B)
                dp[i][J][1] = o+A*abs(J-j)+B;

            if (dp[i][J][1] > o+C*abs(J-j))
                dp[i][J][1] = o+C*abs(J-j);

            int update = min(o+C*abs(J-j),
                            dp[i][J][0]+dp[i][J][1]);
            if (dp[i][J][2] > update)
                dp[i][J][2] = update;
            
            if (flg0) q.insert({dp[i][J][2],i,J,0});
            if (flg2) q.insert({dp[i][J][2],i,J,2});
        }
    }
}

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

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

    iN();
    Dijkstra();
    ouT();
}

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