Submission #1298889

#TimeUsernameProblemLanguageResultExecution timeMemory
1298889chikien2009Soccer (JOI17_soccer)C++20
100 / 100
346 ms22004 KiB
#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const int di[4] = {0, 0, -1, 1};
const int dj[4] = {-1, 1, 0, 0};

int h, w, n;
long long a, b, c;
long long cost[501][501], f[501][501][5];
pair<int, int> p[100000];

inline void CalculateCost()
{
    priority_queue<pair<long long, pair<int, int>>> pq;
    int x, y, nxt_x, nxt_y;
    long long z;

    for (int i = 0; i <= h; ++i)
    {
        fill_n(cost[i], w + 1, 1e18);
    }
    for (int i = 0; i < n; ++i)
    {
        cost[p[i].first][p[i].second] = 0;
        pq.push({0, p[i]});
    }
    while (!pq.empty())
    {
        z = -pq.top().first;
        x = pq.top().second.first;
        y = pq.top().second.second;
        pq.pop();
        if (cost[x][y] != z)
        {
            continue;
        }
        for (int i = 0; i < 4; ++i)
        {
            nxt_x = x + di[i];
            nxt_y = y + dj[i];
            if (0 <= nxt_x && nxt_x <= h && 0 <= nxt_y && nxt_y <= w &&
                cost[nxt_x][nxt_y] > cost[x][y] + c)
            {
                cost[nxt_x][nxt_y] = cost[x][y] + c;
                pq.push({-cost[nxt_x][nxt_y], {nxt_x, nxt_y}});
            }
        }
    }
}

inline void CalculateResult()
{
    long long v;
    int x, y, z, nxt_x, nxt_y;
    priority_queue<pair<long long, array<int, 3>>> pq;
    for (int i = 0; i <= h; ++i)
    {
        for (int j = 0; j <= w; ++j)
        {
            fill_n(f[i][j], 5, 1e18);
        }
    }
    f[p[0].first][p[0].second][4] = 0;
    pq.push({0, {p[0].first, p[0].second, 4}});
    while (!pq.empty())
    {
        v = -pq.top().first;
        x = pq.top().second[0];
        y = pq.top().second[1];
        z = pq.top().second[2];
        pq.pop();
        if (v != f[x][y][z])
        {
            continue;
        }
        if (z == 4)
        {
            for (int i = 0; i < 4; ++i)
            {
                nxt_x = x + di[i];
                nxt_y = y + dj[i];
                if (0 <= nxt_x && nxt_x <= h && 0 <= nxt_y && nxt_y <= w)
                {
                    if (f[nxt_x][nxt_y][i] > f[x][y][z] + a + b)
                    {
                        f[nxt_x][nxt_y][i] = f[x][y][z] + a + b;
                        pq.push({-f[nxt_x][nxt_y][i], {nxt_x, nxt_y, i}});
                    }
                    if (f[nxt_x][nxt_y][z] > f[x][y][z] + c)
                    {
                        f[nxt_x][nxt_y][z] = f[x][y][z] + c;
                        pq.push({-f[nxt_x][nxt_y][z], {nxt_x, nxt_y, z}});
                    }
                }
            }
            continue;
        }
        if (f[x][y][4] > f[x][y][z] + cost[x][y])
        {
            f[x][y][4] = f[x][y][z] + cost[x][y];
            pq.push({-f[x][y][4], {x, y, 4}});
        }
        nxt_x = x + di[z];
        nxt_y = y + dj[z];
        if (0 <= nxt_x && nxt_x <= h && 0 <= nxt_y && nxt_y <= w &&
            f[nxt_x][nxt_y][z] > f[x][y][z] + a)
        {
            f[nxt_x][nxt_y][z] = f[x][y][z] + a;
            pq.push({-f[nxt_x][nxt_y][z], {nxt_x, nxt_y, z}});
        }
    }
}

int main()
{
    setup();

    cin >> h >> w >> a >> b >> c >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> p[i].first >> p[i].second;
    }
    CalculateCost();
    CalculateResult();
    // for (int i = 0; i <= h; ++i)
    // {
    //     for (int j = 0; j <= w; ++j)
    //     {
    //         cout << cost[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";
    // for (int i = 0; i <= h; ++i)
    // {
    //     for (int j = 0; j <= w; ++j)
    //     {
    //         cout << f[i][j][4] << " ";
    //     }
    //     cout << "\n";
    // }
    cout << f[p[n - 1].first][p[n - 1].second][4];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...