結果
問題 | No.2328 Build Walls |
ユーザー | InTheBloom |
提出日時 | 2023-07-21 13:37:29 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 1,040 ms / 3,000 ms |
コード長 | 2,613 bytes |
コンパイル時間 | 2,748 ms |
コンパイル使用メモリ | 178,944 KB |
実行使用メモリ | 118,260 KB |
最終ジャッジ日時 | 2024-09-21 15:38:30 |
合計ジャッジ時間 | 17,664 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 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 | 2 ms
5,376 KB |
testcase_08 | AC | 2 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 | 1 ms
5,376 KB |
testcase_13 | AC | 365 ms
64,384 KB |
testcase_14 | AC | 263 ms
32,768 KB |
testcase_15 | AC | 237 ms
33,152 KB |
testcase_16 | AC | 46 ms
9,856 KB |
testcase_17 | AC | 267 ms
39,552 KB |
testcase_18 | AC | 8 ms
5,376 KB |
testcase_19 | AC | 45 ms
11,648 KB |
testcase_20 | AC | 23 ms
5,760 KB |
testcase_21 | AC | 273 ms
56,064 KB |
testcase_22 | AC | 404 ms
46,336 KB |
testcase_23 | AC | 948 ms
118,144 KB |
testcase_24 | AC | 942 ms
118,144 KB |
testcase_25 | AC | 964 ms
118,144 KB |
testcase_26 | AC | 844 ms
118,144 KB |
testcase_27 | AC | 914 ms
118,144 KB |
testcase_28 | AC | 545 ms
118,168 KB |
testcase_29 | AC | 920 ms
118,152 KB |
testcase_30 | AC | 671 ms
118,232 KB |
testcase_31 | AC | 662 ms
118,144 KB |
testcase_32 | AC | 883 ms
118,144 KB |
testcase_33 | AC | 1,040 ms
118,256 KB |
testcase_34 | AC | 711 ms
118,260 KB |
testcase_35 | AC | 982 ms
118,144 KB |
testcase_36 | AC | 2 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!(toNode[], "a.totalCost > b.totalCost") PQ = new toNode[](H*W); // 最初の一列はタダで張れるので、最初の一列のどこかを確定頂点にする 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)); } }