제출 #397289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397289		timmyfeng	Soccer (JOI17_soccer)	C++17	100 / 100	547 ms	22052 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

const int X[] = {1, 0, -1, 0}, Y[] = {0, 1, 0, -1};
const int N = 501, M = 100001;

priority_queue<array<long long, 4>> dijkstra;
long long player[N][N], dist[N][N][5];
array<int, 2> coord[M];
int h, w;

void update(int x, int y, int z, long long d) {
    if (0 <= x && x <= h && 0 <= y && y <= w && d < dist[x][y][z]) {
        dist[x][y][z] = d;
        dijkstra.push({-d, x, y, z});
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long a, b, c;
    cin >> h >> w >> a >> b >> c >> n;

    for (int i = 0; i <= h; ++i) {
        for (int j = 0; j <= w; ++j) {
            player[i][j] = -1;
            for (int k = 0; k < 5; ++k) {
                dist[i][j][k] = LLONG_MAX;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        auto &[x, y] = coord[i];
        cin >> x >> y;
    }

    queue<array<int, 2>> bfs;
    for (int i = 0; i < n - 1; ++i) {
        auto [x, y] = coord[i];
        if (player[x][y] == -1) {
            player[x][y] = 0;
            bfs.push({x, y});
        }
    }

    while (!bfs.empty()) {
        auto [x, y] = bfs.front();
        bfs.pop();
        for (int i = 0; i < 4; ++i) {
            int xn = x + X[i];
            int yn = y + Y[i];
            if (0 <= xn && xn <= h && 0 <= yn && yn <= w && player[xn][yn] == -1) {
                player[xn][yn] = player[x][y] + c;
                bfs.push({xn, yn});
            }
        }
    }
    player[coord[n - 1][0]][coord[n - 1][1]] = 0;

    dijkstra.push({0, coord[0][0], coord[0][1], 4});
    dist[coord[0][0]][coord[0][1]][4] = 0;

    while (!dijkstra.empty()) {
        auto [d, x, y, z] = dijkstra.top();
        dijkstra.pop();
        d = -d;

        if (d > dist[x][y][z]) {
            continue;
        }

        if (z == 4) {
            for (int i = 0; i < 4; ++i) {
                update(x, y, i, d + b);
                int xn = x + X[i];
                int yn = y + Y[i];
                update(xn, yn, 4, d + c);
            }
        } else {
            int xn = x + X[z];
            int yn = y + Y[z];
            update(xn, yn, z, d + a);
            update(x, y, 4, d + player[x][y]);
        }
    }

    cout << dist[coord[n - 1][0]][coord[n - 1][1]][4] << "\n";
}

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