結果
問題 | No.2095 High Rise |
ユーザー |
👑 ![]() |
提出日時 | 2022-10-07 22:06:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,303 ms / 2,000 ms |
コード長 | 1,336 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 82,260 KB |
実行使用メモリ | 198,764 KB |
最終ジャッジ日時 | 2024-06-12 18:38:11 |
合計ジャッジ時間 | 9,781 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
from heapq import heappop,heappush class Heap_Point: def __init__(self,x,d): self.d=d self.x=x def __str__(self): return "(point:{}, dist:{})".format(self.x,self.d) def __repr__(self): return str(self) def __lt__(self,other): return self.d<other.d def __iter__(self): yield from (self.x,self.d) #================================================== def solve(): N,M=map(int,input().split()) A=[] for _ in range(N): A.append(list(map(int,input().split()))) if N==1: return 0 inf=float("inf") T=[[inf]*M for _ in range(N)] U=[inf]*N; U[0]=0 Q=[Heap_Point((0,-1),0)] while Q: (i,j),cost=heappop(Q) if i==N-1: return cost if j==-1: Ai=A[i]; Ti=T[i] for k in range(M): if Ti[k]>cost+Ai[k]: Ti[k]=cost+Ai[k] heappush(Q,Heap_Point((i,k),Ti[k])) else: alpha=cost+A[i+1][j] if T[i+1][j]>alpha: T[i+1][j]=alpha heappush(Q, Heap_Point((i+1,j),T[i+1][j])) if U[i+1]>alpha: U[i+1]=alpha heappush(Q, Heap_Point((i+1,-1),U[i+1])) #================================================== print(solve())