제출 #1352782

#제출 시각아이디문제언어결과실행 시간메모리
1352782nagorn_phSoccer (JOI17_soccer)C++20
100 / 100
285 ms25704 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int N = 2e5 + 5;

void solve(){
    int n, m; cin >> n >> m;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    int a, b, c; cin >> a >> b >> c;
    int k; cin >> k;
    vector <pii> p(k);
    int sx = -1, sy = -1, ex = -1, ey = -1;
    queue <pii> q;
    int dis[n+1][m+1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dis[i][j] = inf;
        }
    }
    for (auto &[x, y] : p) {
        cin >> x >> y;
        if (sx == -1) sx = x, sy = y;
        ex = x, ey = y;
        q.emplace(x, y);
        dis[x][y] = 0;
    }
    // cout << sx << " " << sy << " -> " << ex << " " << ey << "\n";
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx > n || ny < 0 || ny > m || dis[nx][ny] <= dis[x][y] + 1) continue;
            dis[nx][ny] = dis[x][y] + 1;
            q.emplace(nx, ny);
        }
    }
    priority_queue <tiiii, vector <tiiii>, greater <tiiii>> pq;
    pq.emplace(0, sx, sy, 0);
    int dp[n+1][m+1][6];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int l = 0; l < 6; l++) {
                dp[i][j][l] = inf;
            }
        }
    }
    dp[sx][sy][0] = 0;
    while (!pq.empty()) {
        auto [w, x, y, di] = pq.top(); pq.pop();
        if (w > dp[x][y][di]) continue;
        // cout << x << " " << y << " : " << di << " == " << w << "\n";
        if (di == 0) {
            for (int i = 1; i <= 4; i++) {
                if (dp[x][y][i] <= dp[x][y][di] + b) continue;
                dp[x][y][i] = dp[x][y][di] + b;
                pq.emplace(dp[x][y][i], x, y, i);
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx > n || ny < 0 || ny > m || dp[nx][ny][0] <= dp[x][y][0] + c) continue;
                dp[nx][ny][0] = dp[x][y][0] + c;
                pq.emplace(dp[nx][ny][0], nx, ny, 0);
            }
        }
        else {
            int nx = x + dx[di - 1], ny = y + dy[di - 1];
            if (!(nx < 0 || nx > n || ny < 0 || ny > m || dp[nx][ny][di] <= dp[x][y][di] + a)) {
                dp[nx][ny][di] = dp[x][y][di] + a;
                pq.emplace(dp[nx][ny][di], nx, ny, di);
            }
            if (dp[x][y][0] > dp[x][y][di] + dis[x][y] * c) {
                dp[x][y][0] = dp[x][y][di] + dis[x][y] * c;
                pq.emplace(dp[x][y][0], x, y, 0);
            }
        }
    }
    cout << *min_element(dp[ex][ey], dp[ex][ey] + 5);
}

int32_t main(){
    iShowSpeed;
    // int q; cin >> q; while (q--) 
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...