Submission #253376

#	Time	Username	Problem	Language	Result	Execution time	Memory
253376		Tuk1352	Soccer (JOI17_soccer)	C++11	100 / 100	620 ms	36072 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int H, W, n;
    cin >> H >> W;
    long long A, B, C;
    cin >> A >> B >> C >> n;
    long long Y[n], X[n];
    long long D[5][H+1][W+1], G[5][H+1][W+1], Di[H+1][W+1], Gd[H+1][W+1];
    for (int y = 0; y <= H; y++)
    {
        for (int u = 0; u <= W; u++)
        {
            Di[y][u] = 2000000000000;
            Gd[y][u] = 1;
            for (int i = 0; i < 5; i++)
            {
                D[i][y][u] = 2000000000000000000;
                G[i][y][u] = 1;
            }
        }
    }
    vector <pair<int,int>> T;
    for (int i = 0; i < n; i++)
    {
        cin >> Y[i] >> X[i];
        Di[Y[i]][X[i]] = 0;
        if (Gd[Y[i]][X[i]] == 1)
        {
            Gd[Y[i]][X[i]] = 0;
            T.push_back({Y[i],X[i]});
        }
    }
    for (int i = 0; i < T.size(); i++)
    {
        int I = T[i].first;
        int Y = T[i].second;
        if (I > 0 && Gd[I-1][Y] == 1)
        {
            Gd[I-1][Y] = 0;
            Di[I-1][Y] = Di[I][Y] + 1;
            T.push_back({I-1,Y});
        }
        if (Y > 0 && Gd[I][Y-1] == 1)
        {
            Gd[I][Y-1] = 0;
            Di[I][Y-1] = Di[I][Y] + 1;
            T.push_back({I,Y-1});
        }
        if (I <= H-1 && Gd[I+1][Y] == 1)
        {
            Gd[I+1][Y] = 0;
            Di[I+1][Y] = Di[I][Y] + 1;
            T.push_back({I+1,Y});
        }
        if (Y <= W-1 && Gd[I][Y+1] == 1)
        {
            Gd[I][Y+1] = 0;
            Di[I][Y+1] = Di[I][Y] + 1;
            T.push_back({I,Y+1});
        }
    }
    priority_queue <pair<pair<long long, int>,pair<int, int>>, vector<pair<pair<long long, int>,pair<int, int>>>, greater<pair<pair<long long, int>,pair<int, int>>>> Q;
    D[0][Y[0]][X[0]] = 0;
    Q.push({{0,0},{Y[0],X[0]}});
    while (Q.size() > 0)
    {
        int I = Q.top().second.first;
        int Y = Q.top().second.second;
        int d = Q.top().first.first;
        int t = Q.top().first.second;
        Q.pop();
        if (G[t][I][Y] == 0)
        {
            continue;
        }
        G[t][I][Y] = 0;
        if (t == 0)
        {
            if (I > 0 && D[0][I][Y] + C < D[0][I-1][Y])
            {
                D[0][I-1][Y] = D[0][I][Y] + C;
                Q.push({{D[0][I-1][Y],0},{I-1,Y}});
            }
            if (Y > 0 && D[0][I][Y] + C < D[0][I][Y-1])
            {
                D[0][I][Y-1] = D[0][I][Y] + C;
                Q.push({{D[0][I][Y-1],0},{I,Y-1}});
            }
            if (I <= H-1 && D[0][I][Y] + C < D[0][I+1][Y])
            {
                D[0][I+1][Y] = D[0][I][Y] + C;
                Q.push({{D[0][I+1][Y],0},{I+1,Y}});
            }
            if (Y <= W-1 && D[0][I][Y] + C < D[0][I][Y+1])
            {
                D[0][I][Y+1] = D[0][I][Y] + C;
                Q.push({{D[0][I][Y+1],0},{I,Y+1}});
            }
            for (int i = 1; i <= 4; i++)
            {
                if (D[0][I][Y] + B < D[i][I][Y])
                {
                    D[i][I][Y] = D[0][I][Y] + B;
                    Q.push({{D[i][I][Y],i},{I,Y}});
                }
            }
        }
        else
        {
            if (D[t][I][Y] + Di[I][Y]*C < D[0][I][Y])
            {
                D[0][I][Y] = D[t][I][Y] + Di[I][Y]*C;
                Q.push({{D[0][I][Y],0},{I,Y}});
            }
            if (t == 1)
            {
                if (I > 0 && D[t][I][Y] + A < D[t][I-1][Y])
                {
                    D[t][I-1][Y] = D[t][I][Y] + A;
                    Q.push({{D[t][I-1][Y],t},{I-1,Y}});
                }
            }
            else if (t == 2)
            {
                if (Y <= W-1 && D[t][I][Y] + A < D[t][I][Y+1])
                {
                    D[t][I][Y+1] = D[t][I][Y] + A;
                    Q.push({{D[t][I][Y+1],t},{I,Y+1}});
                }
            }
            else if (t == 3)
            {
                if (I <= H-1 && D[t][I][Y] + A < D[t][I+1][Y])
                {
                    D[t][I+1][Y] = D[t][I][Y] + A;
                    Q.push({{D[t][I+1][Y],t},{I+1,Y}});
                }
            }
            else if (t == 4)
            {
                if (Y > 0 && D[t][I][Y] + A < D[t][I][Y-1])
                {
                    D[t][I][Y-1] = D[t][I][Y] + A;
                    Q.push({{D[t][I][Y-1],t},{I,Y-1}});
                }
            }
        }
    }
    long long Re = D[0][Y[n-1]][X[n-1]];
    for (int i = 1; i <= 4; i++)
    {
        Re = min(Re, D[i][Y[n-1]][X[n-1]]);
    }
    cout << Re;
    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < T.size(); i++)
                     ~~^~~~~~~~~~
soccer.cpp:72:13: warning: unused variable 'd' [-Wunused-variable]
         int d = Q.top().first.first;
             ^

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