結果
問題 | No.2328 Build Walls |
ユーザー | tyawanmusi |
提出日時 | 2023-05-24 10:12:31 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,279 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 86,816 KB |
実行使用メモリ | 360,704 KB |
最終ジャッジ日時 | 2023-08-25 02:38:51 |
合計ジャッジ時間 | 19,100 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,684 KB |
testcase_01 | AC | 74 ms
71,284 KB |
testcase_02 | AC | 76 ms
71,296 KB |
testcase_03 | AC | 79 ms
71,312 KB |
testcase_04 | AC | 75 ms
71,336 KB |
testcase_05 | AC | 75 ms
71,424 KB |
testcase_06 | AC | 74 ms
71,248 KB |
testcase_07 | AC | 74 ms
71,656 KB |
testcase_08 | AC | 75 ms
71,288 KB |
testcase_09 | AC | 76 ms
71,620 KB |
testcase_10 | AC | 73 ms
71,296 KB |
testcase_11 | AC | 74 ms
71,348 KB |
testcase_12 | AC | 74 ms
71,420 KB |
testcase_13 | AC | 1,508 ms
221,364 KB |
testcase_14 | AC | 798 ms
144,176 KB |
testcase_15 | AC | 886 ms
149,076 KB |
testcase_16 | AC | 277 ms
93,476 KB |
testcase_17 | AC | 1,111 ms
172,540 KB |
testcase_18 | AC | 147 ms
80,160 KB |
testcase_19 | AC | 279 ms
95,652 KB |
testcase_20 | AC | 200 ms
85,132 KB |
testcase_21 | AC | 1,094 ms
195,352 KB |
testcase_22 | AC | 1,116 ms
173,936 KB |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | AC | 2,141 ms
329,344 KB |
testcase_29 | TLE | - |
testcase_30 | AC | 2,915 ms
345,768 KB |
testcase_31 | AC | 2,555 ms
342,036 KB |
testcase_32 | TLE | - |
testcase_33 | AC | 2,594 ms
326,532 KB |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | AC | 75 ms
71,552 KB |
ソースコード
from heapq import heappop, heappush def dijkstra(s, n, edge): inf = float("inf") ans = [inf] * n ans[s] = 0 root = [-1] * n h = [[0, s]] while h: c, v = heappop(h) if ans[v] < c: continue for u, t in edge[v]: if c + t < ans[u]: ans[u] = c + t root[u] = v heappush(h, [c + t, u]) return [ans, root] 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, (h - 2) * w + 2, edge)[0] if ans[(h - 2) * w + 1] >= inf: print(-1) else: print(ans[(h - 2) * w + 1])