結果

問題 No.2328 Build Walls
ユーザー InTheBloom
提出日時 2023-12-20 00:37:23
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,059 ms / 3,000 ms
コード長 3,139 bytes
コンパイル時間 4,097 ms
コンパイル使用メモリ 216,064 KB
実行使用メモリ 131,996 KB
最終ジャッジ日時 2024-09-27 09:04:05
合計ジャッジ時間 13,124 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Dijkstra
{
    import std.container : BinaryHeap;
    import std.typecons;
    import std.format : format;

    size_t N;
    long[] cost;
    size_t[][] graph;
    long delegate (int, int) getCost;
    BinaryHeap!(Tuple!(size_t, long)[], "b[1]<a[1]") PQ;

    this (size_t N) {
        this.N = N;
        graph = new size_t[][](N, 0);
        cost = new long[](N);

        Tuple!(size_t, long)[] buf; buf.reserve(N);
        PQ = buf;

        cost[] = long.max;
    }

    // cost setter
    void setCostFunc (long delegate (int, int) func) { this.getCost = func; }

    void addEdge (size_t u, size_t v)
    in {
        assert(u < N, format("Dijkstra.addEdge : out of range. N = %s, u = %s.", N, u));
        assert(v < N, format("Dijkstra.addEdge : out of range. N = %s, v = %s.", N, v));
    }
    do {
        graph[u] ~= v;
    }
    void setStartPoint (size_t v, long W)
    in {
        assert(v < N, format("Dijkstra.addEdge : out of range. N = %s, u = %s.", N, v));
    }
    do {
        PQ.insert(tuple(v, W));
    }

    const(long[]) run ()
    in {
        assert(getCost != null, "Dijkstra.run : function getCost is undefined.");
    }
    do {
        while (!PQ.empty) {
            auto head = PQ.front; PQ.removeFront;
            size_t v = head[0]; long w = head[1];
            if (cost[v] < w) continue;

            cost[v] = w;
            foreach (to; graph[v]) {
                long NewCost = cost[v] + getCost(cast(int) v, cast(int) to);
                if (cost[to] <= NewCost) continue;
                cost[to] = NewCost;
                PQ.insert(tuple(to, NewCost));
            }
        }

        return cost;
    }
}

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

    solve(H, W, A);
}

void solve (int H, int W, int[][] A) {
    int f (int y, int x) {
        return y*W + x;
    }
    Tuple!(int, int) finv (int x) {
        return tuple(x/W, x%W);
    }
    long getCost (int from, int to) {
        auto t = finv(to);
        return A[t[0]][t[1]];
    }
    bool isInGrid (int y, int x) {
        return 0 <= y && y < H-2 && 0 <= x && x < W;
    }

    auto dij = new Dijkstra((H-2)*W);
    dij.setCostFunc(&getCost);

    const int[] dxy = [-1, 0, 1];

    foreach (i; 0..H-2) foreach (j; 0..W) {
        if (A[i][j] == -1) continue;
        foreach (dy; dxy) foreach (dx; dxy) if (abs(dy) != 0 || abs(dx) != 0) {
            int y = i + dy, x = j + dx;
            if (!isInGrid(y, x)) continue;
            if (A[y][x] == -1) continue;
            dij.addEdge(f(i, j), f(y, x));
        }
    }
    foreach (i; 0..H-2) {
        if (A[i][0] == -1) continue;
        dij.setStartPoint(f(i, 0), A[i][0]);
    }

    auto res = dij.run;

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

    if (ans == long.max) {
        writeln(-1);
    }
    else {
        writeln(ans);
    }
}

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