結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2020-08-20 22:23:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 125 ms / 5,000 ms |
コード長 | 1,091 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 82,536 KB |
実行使用メモリ | 79,492 KB |
最終ジャッジ日時 | 2024-07-01 09:53:43 |
合計ジャッジ時間 | 4,132 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import heapq #edgeには[weight,v]を追加していく def dijkstra(s,edge): #始点sから各頂点への最短距離 d = [float("inf")] * (n+1) used = [True] * (n+1) #True:未確定 d[s] = 0 used[s] = False edgelist = [] for e in edge[s]: heapq.heappush(edgelist,e) while len(edgelist): minedge = heapq.heappop(edgelist) #まだ使われてない頂点の中から最小の距離のものを探す if not used[minedge[1]]: continue v = minedge[1] d[v] = minedge[0] used[v] = False for e in edge[v]: if used[e[1]]: heapq.heappush(edgelist,[e[0]+d[v],e[1]]) return d def popcount(n): ret=0 for i in range(20): if n&(1<<i): ret+=1 return ret n=int(input()) edges=[[] for _ in range(n+1)] for v in range(1,n+1): pc=popcount(v) if v-pc>=1: edges[v].append((1,v-pc)) if v+pc<=n: edges[v].append((1,v+pc)) ans=dijkstra(1,edges) if ans[n]==float('inf'): print(-1) else: print(ans[n]+1)