結果
問題 | No.2328 Build Walls |
ユーザー | InTheBloom |
提出日時 | 2023-07-21 13:37:29 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 866 ms / 3,000 ms |
コード長 | 2,613 bytes |
コンパイル時間 | 5,258 ms |
コンパイル使用メモリ | 169,288 KB |
実行使用メモリ | 119,312 KB |
最終ジャッジ日時 | 2023-10-21 14:23:46 |
合計ジャッジ時間 | 13,701 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 1 ms
4,348 KB |
testcase_05 | AC | 2 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 | 1 ms
4,348 KB |
testcase_11 | AC | 1 ms
4,348 KB |
testcase_12 | AC | 1 ms
4,348 KB |
testcase_13 | AC | 278 ms
64,984 KB |
testcase_14 | AC | 210 ms
34,980 KB |
testcase_15 | AC | 184 ms
34,968 KB |
testcase_16 | AC | 35 ms
12,020 KB |
testcase_17 | AC | 209 ms
41,112 KB |
testcase_18 | AC | 6 ms
4,348 KB |
testcase_19 | AC | 35 ms
11,756 KB |
testcase_20 | AC | 17 ms
7,404 KB |
testcase_21 | AC | 221 ms
57,532 KB |
testcase_22 | AC | 324 ms
49,544 KB |
testcase_23 | AC | 755 ms
119,312 KB |
testcase_24 | AC | 745 ms
119,312 KB |
testcase_25 | AC | 757 ms
119,312 KB |
testcase_26 | AC | 667 ms
119,312 KB |
testcase_27 | AC | 716 ms
119,312 KB |
testcase_28 | AC | 424 ms
119,312 KB |
testcase_29 | AC | 745 ms
119,312 KB |
testcase_30 | AC | 525 ms
119,312 KB |
testcase_31 | AC | 515 ms
119,312 KB |
testcase_32 | AC | 709 ms
119,312 KB |
testcase_33 | AC | 866 ms
119,312 KB |
testcase_34 | AC | 562 ms
119,312 KB |
testcase_35 | AC | 794 ms
119,312 KB |
testcase_36 | AC | 1 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!(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)); } }