Submission #11232040

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;
using P = array<int, 2>;
const int dh[]{1, 0, -1, 0}, dw[]{0, 1, 0, -1};

int H, W;

inline bool in(int h, int w) { return 0 <= h && h < H && 0 <= w && w < W; }

int main() {
    int N;
    ll A, B, C;
    cin >> H >> W >> A >> B >> C >> N;
    H++;
    W++;
    int d0[H][W];
    memset(d0, -1, sizeof(d0));
    queue<P> que;
    int sh, sw, th, tw;
    for(int i = 0; i < N; i++) {
        cin >> th >> tw;
        if(!i) sh = th, sw = tw;
        que.push(P{th, tw});
        d0[th][tw] = 0;
    }
    while(!que.empty()) {
        P p = que.front();
        que.pop();
        for(int i = 0; i < 4; i++) {
            int nh = p[0] + dh[i];
            int nw = p[1] + dw[i];
            if(in(nh, nw) && d0[nh][nw] == -1) {
                d0[nh][nw] = d0[p[0]][p[1]] + 1;
                que.push(P{nh, nw});
            }
        }
    }

    V<V<V<ll>>> d(H, V<V<ll>>(W, V<ll>(5, 1LL << 60)));
    struct st {
        int h, w, v;
        ll d;
        inline bool operator<(const st &r) const { return d > r.d; }
    };
    d[sh][sw][4] = 0;
    priority_queue<st> pque;
    pque.push(st{sh, sw, 4, 0});
    while(!pque.empty()) {
        st v = pque.top();
        pque.pop();
        if(d[v.h][v.w][v.v] < v.d) continue;
        if(v.v == 4) {
            for(int i = 0; i < 4; i++) {
                int nh = v.h + dh[i];
                int nw = v.w + dw[i];
                if(in(nh, nw)) {
                    if(d[nh][nw][4] > v.d + C) {
                        d[nh][nw][4] = v.d + C;
                        pque.push(st{nh, nw, 4, v.d + C});
                    }
                    if(d[nh][nw][i] > v.d + A + B) {
                        d[nh][nw][i] = v.d + A + B;
                        pque.push(st{nh, nw, i, v.d + A + B});
                    }
                }
            }
        } else {
            int nh = v.h + dh[v.v];
            int nw = v.w + dw[v.v];
            if(in(nh, nw) && d[nh][nw][v.v] > v.d + A) {
                d[nh][nw][v.v] = v.d + A;
                pque.push(st{nh, nw, v.v, v.d + A});
            }
            if(d[v.h][v.w][4] > v.d + d0[v.h][v.w] * C) {
                d[v.h][v.w][4] = v.d + d0[v.h][v.w] * C;
                pque.push(st{v.h, v.w, 4, d[v.h][v.w][4]});
            }
        }
    }
    ll ans = 1LL << 60;
    for(int i = 0; i < 5; i++)
        ans = min(ans, d[th][tw][i]);
    cout << ans << endl;
}

Submission Info

Judge Result