結果
問題 | No.2328 Build Walls |
ユーザー | tyawanmusi |
提出日時 | 2023-05-24 10:23:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,315 ms / 3,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 2,113 ms |
コンパイル使用メモリ | 86,880 KB |
実行使用メモリ | 301,564 KB |
最終ジャッジ日時 | 2023-08-25 02:44:27 |
合計ジャッジ時間 | 19,900 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,508 KB |
testcase_01 | AC | 73 ms
71,092 KB |
testcase_02 | AC | 74 ms
71,248 KB |
testcase_03 | AC | 74 ms
71,184 KB |
testcase_04 | AC | 76 ms
71,088 KB |
testcase_05 | AC | 73 ms
71,072 KB |
testcase_06 | AC | 72 ms
71,384 KB |
testcase_07 | AC | 74 ms
71,596 KB |
testcase_08 | AC | 75 ms
71,316 KB |
testcase_09 | AC | 74 ms
71,444 KB |
testcase_10 | AC | 73 ms
71,328 KB |
testcase_11 | AC | 75 ms
71,624 KB |
testcase_12 | AC | 77 ms
71,600 KB |
testcase_13 | AC | 424 ms
196,012 KB |
testcase_14 | AC | 438 ms
136,096 KB |
testcase_15 | AC | 390 ms
135,404 KB |
testcase_16 | AC | 192 ms
91,076 KB |
testcase_17 | AC | 426 ms
152,744 KB |
testcase_18 | AC | 130 ms
79,552 KB |
testcase_19 | AC | 137 ms
90,640 KB |
testcase_20 | AC | 167 ms
84,408 KB |
testcase_21 | AC | 332 ms
172,296 KB |
testcase_22 | AC | 589 ms
162,904 KB |
testcase_23 | AC | 1,196 ms
296,300 KB |
testcase_24 | AC | 1,157 ms
301,564 KB |
testcase_25 | AC | 1,169 ms
301,248 KB |
testcase_26 | AC | 1,031 ms
300,908 KB |
testcase_27 | AC | 1,144 ms
301,444 KB |
testcase_28 | AC | 584 ms
300,224 KB |
testcase_29 | AC | 1,172 ms
301,064 KB |
testcase_30 | AC | 712 ms
300,508 KB |
testcase_31 | AC | 689 ms
300,820 KB |
testcase_32 | AC | 1,101 ms
301,276 KB |
testcase_33 | AC | 1,315 ms
301,408 KB |
testcase_34 | AC | 741 ms
300,668 KB |
testcase_35 | AC | 1,182 ms
300,804 KB |
testcase_36 | AC | 72 ms
71,528 KB |
ソースコード
import sys input = sys.stdin.readline from heapq import heappush, heappop def dijkstra(N, G, s): INF = 10**10 dist = [INF] * N que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist h, w = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(h - 2)] def ij(i, j): return i * w + j edge = [[]for _ in range((h - 2) * w + 2)] d = [ [-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1] ] inf = 10**10 for i in range(h - 2): for j in range(w): for di, dj in d: if 0 <= i + di < h - 2 and 0 <= j + dj < w: if a[i + di][j + dj] == -1: edge[ij(i, j)].append((ij(i + di, j + dj), inf)) else: edge[ij(i, j)].append((ij(i + di, j + dj), a[i + di][j + dj])) for i in range(h - 2): if a[i][0] == -1: edge[(h - 2) * w].append((ij(i, 0), inf)) else: edge[(h - 2) * w].append((ij(i, 0), a[i][0])) edge[ij(i, w - 1)].append(((h - 2) * w + 1, 0)) ans = dijkstra((h - 2) * w + 2, edge, (h - 2) * w) if ans[(h - 2) * w + 1] >= inf: print(-1) else: print(ans[(h - 2) * w + 1])