Submission #1305224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305224		sqwiijqk	Soccer (JOI17_soccer)	C++20	0 / 100	74 ms	12136 KiB

soccer

#pragma gcc optimize("Ofast")

#include <vector>

#pragma gcc target("avx, avx2, popcnt, lzcnt")

#include <bits/stdc++.h>
#include <experimental/random>

using namespace std;

void solve1();

using ll = long long;
using ull = unsigned long long;
using ld = double;
using BIG = __int128_t;
# define int long long
# define chmin(a, b) a = min(a, b)
const int MOD = 1e9 + 7;
const int INF = 1e9;

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int qwerty = 1;
    // cin >> qwerty;
    while (qwerty--) {
        solve1();
    }
}

struct Node {
    int x, y;
};

void solve1() {
    int n, m;
    cin >> n >> m;
    n++;
    m++;
    int a, b, c;
    cin >> a >> b >> c;
    int all;
    cin >> all;
    vector<Node> pos(all);
    for (int i = 0; i < all; i++) {
        cin >> pos[i].x >> pos[i].y;
    }
    vector<vector<int>> mn_dist(n, vector<int>(m, INF));
    for (int i = 0; i < all; i++) {
        mn_dist[pos[i].x][pos[i].y] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {
            chmin(mn_dist[i][j], mn_dist[i][j - 1] + c);
        }
        for (int j = m - 2; j >= 0; j--) {
            chmin(mn_dist[i][j], mn_dist[i][j + 1] + c);
        }
    }
    for (int j = 0; j < m; j++) {
        for (int i = 1; i < n; i++) {
            chmin(mn_dist[i][j], mn_dist[i - 1][j] + c);
        }
        for (int i = n - 2; i >= 0; i--) {
            chmin(mn_dist[i][j], mn_dist[i + 1][j] + c);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {
            chmin(mn_dist[i][j], mn_dist[i][j - 1] + c);
        }
        for (int j = m - 2; j >= 0; j--) {
            chmin(mn_dist[i][j], mn_dist[i][j + 1] + c);
        }
    }
    for (int j = 0; j < m; j++) {
        for (int i = 1; i < n; i++) {
            chmin(mn_dist[i][j], mn_dist[i - 1][j] + c);
        }
        for (int i = n - 2; i >= 0; i--) {
            chmin(mn_dist[i][j], mn_dist[i + 1][j] + c);
        }
    }
    vector<int> dist(n * m * 5, INF);
    dist[pos[0].x * m * 5 + pos[0].y * 5] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, pos[0].x * m * 5 + pos[0].y * 5});
    vector<int> dx = {0, 0, 0, -1, 1};
    vector<int> dy = {0, -1, 1, 0, 0};
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        int x = top.second / (m * 5), y = (top.second % (m * 5)) / 5, sost = top.second % 5;
        int dst = top.first;
        if (sost == 0) {
            for (int i = 1; i < 5; i++) {
                int new_z = x * m * 5 + y * 5 + i;
                if (dist[new_z] > dst + mn_dist[x][y] + b) {
                    dist[new_z] = dst + mn_dist[x][y] + b;
                    pq.push({dist[new_z], new_z});
                }
            }
            for (int i = 1; i < 5; i++) {
                int new_x = x + dx[i], new_y = y + dy[i];
                int new_z = new_x * m * 5 + new_y * 5;
                if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && dist[new_z] > dst + c) {
                    dist[new_z] = dst + c;
                    pq.push({dist[new_z], new_z});
                }
            }
        } else {
            int new_x = x + dx[sost];
            int new_y = y + dy[sost];
            if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m) {
                int new_z = new_x * m * 5 + new_y * 5 + sost;
                if (dist[new_z] > dst + a) {
                    dist[new_z] = dst + a;
                    pq.push({dist[new_z], new_z});
                }
            }
            int new_z = x * m * 5 + y * 5;
            if (dist[new_z] > dst) {
                dist[new_z] = dst;
                pq.push({dist[new_z], new_z});
            }
        }
    }
    cout << dist[pos[all - 1].x * m * 5 + pos[all - 1].y * 5];
}

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