結果

問題 No.2328 Build Walls
コンテスト
ユーザー InTheBloom
提出日時 2026-02-03 13:23:21
言語 D
(dmd 2.111.0)
結果
AC  
実行時間 205 ms / 3,000 ms
コード長 2,147 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,011 ms
コンパイル使用メモリ 172,644 KB
実行使用メモリ 15,244 KB
最終ジャッジ日時 2026-02-03 13:23:31
合計ジャッジ時間 7,402 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std;

void main () {
    int H, W;
    readln.read(H, W);
    H -= 2;
    auto A = new int[][](H);
    foreach (i; 0 .. H) {
        A[i] = readln.split.to!(int[]);
    }

    // 1行目からH行目が非連結になるように壁を置く。
    // 壁はすごく迂回したりするかもしれないが、壁が輪のような形状を取ることはない。
    // すなわち、理想の壁において、始点からある壁にたどり着くpathは常に1通りになる。（2通り以上になるとき、自明にコストを削れる。）
    // 以上より、左側から右側への最短経路が解になる。

    auto cost = new long[][](H, W);
    foreach (i; 0 .. H) {
        cost[i][] = long.max;
    }
    auto pq = BinaryHeap!(Tuple!(int, int, long)[], "b[2] < a[2]")([]);
    foreach (i; 0 .. H) {
        if (A[i][0] != -1) {
            cost[i][0] = A[i][0];
            pq.insert(tuple(i, 0, 1L * A[i][0]));
        }
    }

    const dxy = [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
        [1, 1],
        [1, -1],
        [-1, 1],
        [-1, -1]
    ];
    bool isIn (int y, int x) {
        return 0 <= y && y < H && 0 <= x && x < W;
    }

    while (!pq.empty()) {
        auto top = pq.front();
        pq.removeFront();
        int y = top[0];
        int x = top[1];
        long c = top[2];
        if (cost[y][x] < c) {
            continue;
        }

        foreach (d; dxy) {
            int ny = y + d[0];
            int nx = x + d[1];
            if (!isIn(ny, nx) || A[ny][nx] == -1) {
                continue;
            }
            long nc = c + A[ny][nx];

            if (nc < cost[ny][nx]) {
                cost[ny][nx] = nc;
                pq.insert(tuple(ny, nx, nc));
            }
        }
    }

    long ans = long.max;
    foreach (i; 0 .. H) {
        ans = min(ans, cost[i][W - 1]);
    }

    writeln(ans == long.max ? -1 : ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0