Submission #1220521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220521		raphaelp	Soccer (JOI17_soccer)	C++20	0 / 100	1586 ms	327680 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
struct coord
{
    long long x, y;
};
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    long long MAXX = 1000000000000000000;
    long long H, W, A, B, C, N;
    cin >> H >> W >> A >> B >> C >> N;
    queue<pair<long long, long long>> Q;
    vector<vector<long long>> dist(H + 1, vector<long long>(W + 1, -1));
    vector<coord> trans = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    long long targx, targy, startx, starty;
    for (long long i = 0; i < N; i++)
    {
        long long x, y;
        cin >> x >> y;
        if (i == 0)
            startx = x, starty = y;
        targx = x, targy = y;
        if (dist[x][y] == 0)
            continue;
        Q.push({x, y});
        dist[x][y] = 0;
    }
    while (!Q.empty())
    {
        long long x = Q.front().first, y = Q.front().second;
        Q.pop();
        for (long long i = 0; i < 4; i++)
        {
            if (x + trans[i].x >= 0 && x + trans[i].x <= H && y + trans[i].y >= 0 && y + trans[i].y <= W)
            {
                if (dist[x + trans[i].x][y + trans[i].y] != -1)
                    continue;
                dist[x + trans[i].x][y + trans[i].y] = dist[x][y] + 1;
                Q.push({x + trans[i].x, y + trans[i].y});
            }
        }
    }
    vector<vector<long long>> dp(H + 1, vector<long long>(W + 1, MAXX));
    priority_queue<vector<long long>> PQ;
    PQ.push({0, startx, starty});
    while (!PQ.empty())
    {
        long long x = PQ.top()[1], y = PQ.top()[2], t = -PQ.top()[0];
        PQ.pop();
        if (dp[x][y] != MAXX)
            continue;
        dp[x][y] = t;
        if (x == targx && y == targy)
        {
            cout << dp[targx][targy];
            return 0;
        }
        for (long long i = 0; i < 4; i++)
        {
            if (x + trans[i].x >= 0 && x + trans[i].x <= H && y + trans[i].y >= 0 && y + trans[i].y <= W)
            {
                PQ.push({-(t + C), x + trans[i].x, y + trans[i].y});
            }
            long long x2 = x + trans[i].x, y2 = y + trans[i].y;
            while (x2 >= 0 && x2 <= H && y2 >= 0 && y2 <= W)
            {
                if ((dist[x2][y2] * C + t + B + (abs(x - x2) + abs(y - y2)) * A) < dp[x2][y2])
                    PQ.push({-(dist[x2][y2] * C + t + B + (abs(x - x2) + abs(y - y2)) * A), x2, y2});
                x2 += trans[i].x, y2 += trans[i].y;
            }
        }
    }
}

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