結果
問題 | No.971 いたずらっ子 |
ユーザー | Kazun |
提出日時 | 2022-01-03 02:33:34 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,559 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 287,344 KB |
最終ジャッジ日時 | 2024-10-12 08:43:14 |
合計ジャッジ時間 | 7,636 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
ソースコード
class Dijkstra_Heap: inf=float("inf") def __init__(self,N): """ ダイクストラ専用のヒープを生成する. """ self.N=N self.remain=N self.value=[Dijkstra_Heap.inf]*N self.dist=[-1]*N self.tree=list(range(N)) self.inverse=list(range(N)) def __bool__(self): return self.value[0]<Dijkstra_Heap.inf def __swap(self, i, j): """ ヒープ木の第 i 要素と第 j 要素を交換する. """ self.value[i],self.value[j]=self.value[j],self.value[i] p=self.tree[i]; q=self.tree[j] self.tree[i],self.tree[j]=q,p self.inverse[p],self.inverse[q]=j,i def pop(self): assert bool(self.remain) p=self.tree[0] d=self.value[0] self.dist[p]=d self.remain-=1 self.__swap(0,self.remain) self.value[self.remain]=Dijkstra_Heap.inf V=self.value k=0 while True: if 2*k+1>=self.N: break if 2*k+2==self.N: if V[k]<=V[2*k+1]: break j=2*k+1 else: u=V[2*k+1]; v=V[2*k+2] if V[k]<=u and V[k]<=v: break if u<=v: j=2*k+1 else: j=2*k+2 self.__swap(k,j) k=j return (p,d) def __setitem__(self, index, value): if self.dist[index]!=-1: return V=self.value i=self.inverse[index] if V[i]<=value: return V[i]=value while i>0 and V[(i-1)>>1]>V[i]: j=(i-1)>>1 self.__swap(i,j) i=j def __getitem__(self, index): return self.dist[index] if self.dist[index]>=0 else self.value[self.inverse[index]] def final_answer(self, index,default): return self.dist[index] if self.dist[index]>=0 else default #================================================== H,W=map(int,input().split()) A=[] for _ in range(H): A.append(list(map(lambda x:1 if x=="k" else 0,input()))+[-1]) A.append([-1]*(W+1)) Q=Dijkstra_Heap(H*W); Q[0]=0 while Q: x,t=Q.pop() i,j=divmod(x,W) if x==H*W-1: break if i!=H-1: if A[i+1][j]==0: Q[(i+1)*W+j]=t+1 else: Q[(i+1)*W+j]=t+1+((i+1)+j) if j!=W-1: if A[i][j+1]==0: Q[i*W+(j+1)]=t+1 else: Q[i*W+(j+1)]=t+1+(i+(j+1)) print(Q[H*W-1])