結果
問題 | 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 heapqimport sysinput=sys.stdin.readlineds=[[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]]=hfor dx,dy in ds:x,y=px+=dxy+=dyif 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 highH,W=map(int,input().split())A=[]for i in range(H-2):A.append(list(map(int,input().split())))dist=daiku()ans=10**12for 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)