結果
問題 |
No.2328 Build Walls
|
ユーザー |
![]() |
提出日時 | 2025-07-28 01:40:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,299 ms / 3,000 ms |
コード長 | 841 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 100,940 KB |
最終ジャッジ日時 | 2025-07-28 01:41:08 |
合計ジャッジ時間 | 14,640 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sys input = sys.stdin.readline from heapq import heappop,heappush H,W=map(int,input().split()) A=[list(map(int,input().split())) for i in range(H-2)] DP=[[1<<63]*W for i in range(H-2)] Q=[] for i in range(H-2): if A[i][0]!=-1: DP[i][0]=A[i][0] Q.append((DP[i][0],i,0)) Q.sort() while Q: now,x,y=heappop(Q) if DP[x][y]!=now: continue for z in range(x-1,x+2): for w in range(y-1,y+2): if x==z and y==w: continue if 0<=z<H-2 and 0<=w<W: if A[z][w]==-1: continue if now+A[z][w]<DP[z][w]: DP[z][w]=now+A[z][w] heappush(Q,(DP[z][w],z,w)) ANS=1<<63 for i in range(H-2): ANS=min(ANS,DP[i][-1]) if ANS==1<<63: print(-1) else: print(ANS)