結果

問題 No.2328 Build Walls
ユーザー aaaaaaaaaa2230aaaaaaaaaa2230
提出日時 2023-05-28 15:23:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,306 ms / 3,000 ms
コード長 855 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 91,344 KB
最終ジャッジ日時 2024-12-27 06:27:32
合計ジャッジ時間 14,400 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop,heappush
h,w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h-2)]

inf = 10**10
dist = [[inf]*w for i in range(h-2)]

H = []
for i in range(h-2):
    if A[i][0] != -1:
        dist[i][0] = A[i][0]
        heappush(H,[A[i][0],i,0])


while H:
    dis,x,y = heappop(H)
    if dist[x][y] != dis:
        continue

    for dx in range(-1,2):
        for dy in range(-1,2):
            if dx == 0 and dy == 0:
                continue
            nx = x+dx
            ny = y+dy
            if 0 <= nx < h-2 and 0 <= ny < w and A[nx][ny] != -1:
                nd = dis + A[nx][ny]
                if nd < dist[nx][ny]:
                    dist[nx][ny] = nd
                    heappush(H,[nd,nx,ny])


ans = inf
for i in range(h-2):
    ans = min(ans,dist[i][-1])
if ans == inf:
    ans = -1
print(ans)
0