結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:58:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,417 ms / 3,000 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 395 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 99,456 KB |
最終ジャッジ日時 | 2024-12-27 10:09:42 |
合計ジャッジ時間 | 19,662 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import heapq import sys input=sys.stdin.readline ds=[[0,1],[1,1],[-1,1],[1,0],[-1,0],[0,-1],[1,-1],[-1,-1]] def daiku(): hq=[] for i in range(H-2): if A[i][0]!=-1: heapq.heappush(hq,[A[i][0],(i,0)]) high=[-1 for _ in range(W*H)] karidist=[10**9 for _ in range(W*H)] while len(hq)!=0: h,p=heapq.heappop(hq) if high[p[0]*W+p[1]]==-1: high[p[0]*W+p[1]]=h for dx,dy in ds: x,y=p x+=dx y+=dy if 0<=x<H-2 and 0<=y<W and A[x][y]!=-1 and high[x*W+y]==-1: if karidist[x*W+y]>h+A[x][y]: karidist[x*W+y]=h+A[x][y] heapq.heappush(hq,[h+A[x][y],(x,y)]) return high H,W=map(int,input().split()) A=[] for i in range(H-2): A.append(list(map(int,input().split()))) dist=daiku() ans=10**12 for i in range(H-2): if dist[i*W+W-1]!=-1: ans=min(ans,dist[i*W+W-1]) if ans>=10**12: print(-1) else: print(ans)