結果
問題 | No.2328 Build Walls |
ユーザー | InTheBloom |
提出日時 | 2023-07-21 13:23:46 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 839 ms / 3,000 ms |
コード長 | 2,597 bytes |
コンパイル時間 | 1,913 ms |
コンパイル使用メモリ | 177,324 KB |
実行使用メモリ | 108,056 KB |
最終ジャッジ日時 | 2023-10-21 14:11:34 |
合計ジャッジ時間 | 12,924 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 1 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 1 ms
4,348 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,348 KB |
testcase_09 | AC | 1 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 1 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,348 KB |
testcase_13 | AC | 228 ms
60,904 KB |
testcase_14 | AC | 216 ms
30,548 KB |
testcase_15 | AC | 183 ms
31,628 KB |
testcase_16 | AC | 35 ms
11,520 KB |
testcase_17 | AC | 194 ms
36,772 KB |
testcase_18 | AC | 7 ms
4,348 KB |
testcase_19 | AC | 28 ms
11,520 KB |
testcase_20 | AC | 18 ms
7,424 KB |
testcase_21 | AC | 153 ms
51,408 KB |
testcase_22 | AC | 328 ms
45,476 KB |
testcase_23 | AC | 722 ms
108,056 KB |
testcase_24 | AC | 686 ms
108,056 KB |
testcase_25 | AC | 707 ms
108,056 KB |
testcase_26 | AC | 607 ms
108,056 KB |
testcase_27 | AC | 664 ms
108,056 KB |
testcase_28 | AC | 299 ms
108,056 KB |
testcase_29 | AC | 704 ms
108,056 KB |
testcase_30 | AC | 420 ms
108,056 KB |
testcase_31 | AC | 398 ms
108,056 KB |
testcase_32 | AC | 660 ms
108,056 KB |
testcase_33 | AC | 839 ms
108,056 KB |
testcase_34 | AC | 434 ms
108,056 KB |
testcase_35 | AC | 755 ms
108,056 KB |
testcase_36 | AC | 2 ms
4,348 KB |
ソースコード
import std; // 構造体のままダイクストラ(ただし、重みはメンバ変数として管理)を試してみる struct node { int y; int x; int weight; } void main () { // input int H, W; readln.read(H, W); int[][] A = new int[][](H-2, 0); foreach (i; 0..H-2) { A[i] = 0 ~ readln.split.to!(int[]); } // グラフ構築 int[] dxy = [-1, 0, 1]; node[][][] graph = new node[][][](H-2, W+1, 0); foreach (i; 0..H-2) { foreach (j; 0..W+1) { reserve(graph[i][j], 8); // 8方向に辺を張る foreach (dy; dxy) { foreach (dx; dxy) { if (dy == 0 && dx == 0) { continue; } if (H-2 <= i+dy || W+1 <= j+dx || i+dy < 0 || j+dx < 0) { continue; } if (A[i+dy][j+dx] == -1) { continue; } graph[i][j] ~= node(i+dy, j+dx, A[i+dy][j+dx]); } } } } solve(H, W, A, graph); } struct toNode { int y; int x; int totalCost; } void solve (int H, int W, int[][] A, node[][][] graph) { int[][] comfirmedCost = new int[][](H-2, W+1); foreach (ref c; comfirmedCost) { c[] = int.max; } BinaryHeap!(Array!toNode, "a.totalCost > b.totalCost") PQ; // 最初の一列はタダで張れるので、最初の一列のどこかを確定頂点にする PQ.insert(toNode(0, 0, 0)); while (!PQ.empty) { auto shortest = PQ.front; PQ.removeFront; if (comfirmedCost[shortest.y][shortest.x] < shortest.totalCost) { continue; } comfirmedCost[shortest.y][shortest.x] = shortest.totalCost; // 新しく追加された確定頂点から候補を伸ばす foreach (to; graph[shortest.y][shortest.x]) { if (to.weight + shortest.totalCost < comfirmedCost[to.y][to.x]) { PQ.insert(toNode(to.y, to.x, to.weight + shortest.totalCost)); comfirmedCost[to.y][to.x] = to.weight + shortest.totalCost; } } } // 端に到達できたかチェック int ans = int.max; foreach (i; 0..H-2) { ans = min(ans, comfirmedCost[i][W]); } if (ans == int.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)); } }