Sneaking [ZONeエナジー プログラミングコンテスト “HELLO SPACE” E]

https://atcoder.jp/contests/zone2021/tasks/zone2021_e

前提知識

• ダイクストラ

解説

https://atcoder.jp/contests/zone2021/submissions/22237607

ダイクストラをする。遷移についてそのまま実装したら通ってしまった。

本番解法

https://atcoder.jp/contests/zone2021/submissions/22208662

ダイクストラをそのまま実装した解法。
ダイクストラそのものが初めてという人はまずこっちで通してしまってもいいかもしれない。

想定解

想定解法でも通しておいた。
頂点を倍加して、移動中頂点というのを用意しておく。
通常頂点を(y,x)としてとき、移動中頂点を(y+H,x)として定義する。
これで、最後の遷移条件の代わりに以下の条件を追加することで遷移量を減らす。

• 通常頂点(y,x) -> 移動中頂点(y+H,x)にコスト1の辺
• 移動中頂点(y+H,x) -> 移動中頂点(y+H-1,x)にコスト1の辺
• 移動中頂点(y+H,x) -> 通常頂点(y,x)にコスト0の辺

これで移動中頂点を経由して(y,x)から(y-i,x)に移動するとコストi+1かかるようにできる。
後はダイクストラを回せばいい。

int H, W, A[505][505], B[505][505];
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[1005][505];
ll D[1005][505];
ll dijk() {
    rep(y, 0, H * 2) rep(x, 0, W) D[y][x] = infl;
    rep(y, 0, H * 2) rep(x, 0, W) vis[y][x] = 0;

    min_priority_queue<pair<ll, int>> que;

    D[0][0] = 0;
    que.push({ 0, 0 });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll cst = q.first;
        int x = q.second % W;
        int y = q.second / W;

        if (x == W - 1 && y == H - 1) return cst;

        if (vis[y][x]) continue;
        vis[y][x] = 1;

        if (y < H) {
            if (x < W - 1) if (chmin(D[y][x + 1], cst + A[y][x])) que.push({ D[y][x + 1], y * W + x + 1 });
            if (0 < x) if (chmin(D[y][x - 1], cst + A[y][x - 1])) que.push({ D[y][x - 1], y * W + x - 1 });
            if (y < H - 1) if (chmin(D[y + 1][x], cst + B[y][x])) que.push({ D[y + 1][x], (y + 1) * W + x });
            if (chmin(D[y + H][x], cst + 1)) que.push({ D[y + H][x], (y + H) * W + x });
        }
        else {
            if (H < y) if (chmin(D[y - 1][x], cst + 1)) que.push({ D[y - 1][x], (y - 1) * W + x });
            if (chmin(D[y - H][x], cst)) que.push({ D[y - H][x], (y - H) * W + x });
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W - 1) cin >> A[y][x];
    rep(y, 0, H - 1) rep(x, 0, W) cin >> B[y][x];

    cout << dijk() << endl;
}