結果

問題 No.2328 Build Walls
ユーザー InTheBloomInTheBloom
提出日時 2023-12-20 00:37:23
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 1,118 ms / 3,000 ms
コード長 3,139 bytes
コンパイル時間 4,554 ms
コンパイル使用メモリ 204,696 KB
実行使用メモリ 131,196 KB
最終ジャッジ日時 2023-12-20 00:37:39
合計ジャッジ時間 13,607 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 1 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 1 ms
6,676 KB
testcase_09 AC 1 ms
6,676 KB
testcase_10 AC 1 ms
6,676 KB
testcase_11 AC 1 ms
6,676 KB
testcase_12 AC 1 ms
6,676 KB
testcase_13 AC 129 ms
27,616 KB
testcase_14 AC 240 ms
32,560 KB
testcase_15 AC 147 ms
21,628 KB
testcase_16 AC 24 ms
6,676 KB
testcase_17 AC 133 ms
19,356 KB
testcase_18 AC 5 ms
6,676 KB
testcase_19 AC 12 ms
6,676 KB
testcase_20 AC 14 ms
6,676 KB
testcase_21 AC 52 ms
18,972 KB
testcase_22 AC 406 ms
52,036 KB
testcase_23 AC 577 ms
63,948 KB
testcase_24 AC 578 ms
57,708 KB
testcase_25 AC 565 ms
63,948 KB
testcase_26 AC 407 ms
49,388 KB
testcase_27 AC 519 ms
53,548 KB
testcase_28 AC 88 ms
29,944 KB
testcase_29 AC 580 ms
63,948 KB
testcase_30 AC 243 ms
43,332 KB
testcase_31 AC 197 ms
39,172 KB
testcase_32 AC 482 ms
53,548 KB
testcase_33 AC 1,118 ms
131,196 KB
testcase_34 AC 249 ms
45,412 KB
testcase_35 AC 765 ms
78,472 KB
testcase_36 AC 2 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

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