結果
問題 | No.2328 Build Walls |
ユーザー | InTheBloom |
提出日時 | 2023-06-23 19:29:29 |
言語 | D (dmd 2.106.1) |
結果 |
MLE
|
実行時間 | - |
コード長 | 4,176 bytes |
コンパイル時間 | 4,172 ms |
コンパイル使用メモリ | 182,468 KB |
実行使用メモリ | 557,352 KB |
最終ジャッジ日時 | 2024-06-30 23:06:20 |
合計ジャッジ時間 | 19,880 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 277 ms
71,716 KB |
testcase_14 | AC | 561 ms
122,296 KB |
testcase_15 | AC | 306 ms
57,260 KB |
testcase_16 | AC | 45 ms
13,360 KB |
testcase_17 | AC | 271 ms
51,660 KB |
testcase_18 | AC | 8 ms
6,944 KB |
testcase_19 | AC | 21 ms
10,932 KB |
testcase_20 | AC | 24 ms
7,932 KB |
testcase_21 | AC | 82 ms
30,708 KB |
testcase_22 | AC | 956 ms
196,788 KB |
testcase_23 | AC | 1,222 ms
205,152 KB |
testcase_24 | AC | 1,102 ms
180,120 KB |
testcase_25 | AC | 1,195 ms
201,568 KB |
testcase_26 | AC | 876 ms
141,288 KB |
testcase_27 | AC | 1,051 ms
166,796 KB |
testcase_28 | AC | 114 ms
49,180 KB |
testcase_29 | AC | 1,213 ms
206,200 KB |
testcase_30 | AC | 457 ms
119,784 KB |
testcase_31 | AC | 387 ms
103,544 KB |
testcase_32 | AC | 1,032 ms
165,660 KB |
testcase_33 | MLE | - |
testcase_34 | AC | 487 ms
125,732 KB |
testcase_35 | AC | 1,716 ms
315,116 KB |
testcase_36 | AC | 2 ms
6,944 KB |
ソースコード
import std; // ダイクストラ // (H-2)*(W+1)の頂点をおいて、8方向に有向辺を張る void read(T...)(string S, ref T args) { auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } void main () { int H, W; readln.read(H, W); int[][] A = new int[][](H-2, W); foreach (i; 0..H-2) { A[i] = readln.split.to!(int[]); A[i] = 0 ~ A[i]; } solve(H, W, A); } struct pair { int x; int y; } bool isValid (int[][] A, int x, int y) { if (x < 0 || y < 0 || A.length <= y || A[0].length <= x) { return false; } if (A[y][x] == -1) { return false; } return true; } int toInt (pair X, int[][] A) { return cast(int) (X.x * A.length + X.y); } void connectPath (ref Dijkstra G, int[][] A, int x, int y) { int[] dx = [-1, 0, 1]; int[] dy = [-1, 0, 1]; foreach (i; 0..dx.length) { foreach (j; 0..dy.length) { if (i == 1 && j == 1) { continue; } if (isValid(A, x+dx[i], y+dx[j])) { G.input(pair(x, y).toInt(A), pair(x+dx[i], y+dy[j]).toInt(A), A[y+dy[j]][x+dx[i]]); } } } } void solve (int H, int W, int[][] A) { auto G = Dijkstra((H+1)*(W+1)); foreach (X; 0..cast(int)A[0].length) { foreach (Y; 0..cast(int)A.length) { if (A[Y][X] == -1) { continue; } connectPath(G, A, X, Y); } } long ans = long.max; G.calc(pair(0, 0).toInt(A)); foreach (Y2; 0..H-2) { ans = min(ans, G.cost(pair(W, Y2).toInt(A))); //G.trace(pair(W, Y2)).writeln; //writeln(G.cost(pair(W, Y2))); } if (ans == long.max) { writeln(-1); } else { writeln(ans); } } struct Dijkstra { /* data */ int[][] graph; long[int][] weight; bool is_calc = false; struct dijkstra_node { int vertex; long distance; int path; } dijkstra_node[] node; /* methods */ this (int N) { assert(0 <= N); graph = new int[][](N, 0); node = new dijkstra_node[](N); weight.length = N; foreach (i; 0..N) { node[i] = dijkstra_node(i, long.max, i); } } // u, v must be 0-indexed integer. void input (int u, int v, long w) { assert(0 <= u); assert(0 <= v); assert(0 <= w); if (graph.length <= max(u, v)) { graph.length = max(u, v) + 1; } graph[u] ~= v; weight[u][v] = w; if (node.length <= max(u, v)) { node.length = max(u, v) + 1; node[u] = dijkstra_node(u, long.max, u); node[v] = dijkstra_node(v, long.max, v); } } void calc (int start) { assert(start < graph.length); if (is_calc) { foreach (ref x; node) { x.distance = long.max; x.path = x.vertex; } } node[start].distance = 0; BinaryHeap!(dijkstra_node[], "b.distance < a.distance") PQ = []; PQ.insert(node[start]); while (!PQ.empty) { auto begin = PQ.front; PQ.removeFront; if (node[begin.vertex].distance < begin.distance) { continue; } node[begin.vertex] = begin; foreach (ref x; graph[begin.vertex]) { if (node[begin.vertex].distance + weight[begin.vertex][x] < node[x].distance) { node[x].distance = node[begin.vertex].distance + weight[begin.vertex][x]; node[x].path = begin.vertex; PQ.insert(node[x]); } } } } int[] trace (int end) { DList!int Q; int v = end; while (node[v].path != v) { Q.insertFront(v); v = node[v].path; } Q.insertFront(v); int[] res; while (!Q.empty) { res ~= Q.front; Q.removeFront; } return res; } long cost (int end) { return node[end].distance; } }