結果
問題 | No.2328 Build Walls |
ユーザー | InTheBloom |
提出日時 | 2023-07-21 13:23:46 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 878 ms / 3,000 ms |
コード長 | 2,597 bytes |
コンパイル時間 | 4,578 ms |
コンパイル使用メモリ | 188,852 KB |
実行使用メモリ | 107,008 KB |
最終ジャッジ日時 | 2024-09-21 15:25:49 |
合計ジャッジ時間 | 15,264 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 231 ms
58,624 KB |
testcase_14 | AC | 236 ms
29,952 KB |
testcase_15 | AC | 186 ms
30,336 KB |
testcase_16 | AC | 36 ms
9,344 KB |
testcase_17 | AC | 218 ms
35,840 KB |
testcase_18 | AC | 7 ms
5,376 KB |
testcase_19 | AC | 29 ms
10,880 KB |
testcase_20 | AC | 19 ms
5,888 KB |
testcase_21 | AC | 155 ms
50,816 KB |
testcase_22 | AC | 335 ms
42,112 KB |
testcase_23 | AC | 737 ms
106,876 KB |
testcase_24 | AC | 736 ms
106,880 KB |
testcase_25 | AC | 737 ms
107,008 KB |
testcase_26 | AC | 627 ms
106,876 KB |
testcase_27 | AC | 702 ms
106,880 KB |
testcase_28 | AC | 322 ms
107,008 KB |
testcase_29 | AC | 741 ms
106,880 KB |
testcase_30 | AC | 444 ms
107,008 KB |
testcase_31 | AC | 422 ms
106,880 KB |
testcase_32 | AC | 684 ms
106,880 KB |
testcase_33 | AC | 878 ms
106,880 KB |
testcase_34 | AC | 459 ms
106,880 KB |
testcase_35 | AC | 790 ms
107,008 KB |
testcase_36 | AC | 1 ms
5,376 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)); } }