結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:17:14 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,139 bytes |
コンパイル時間 | 745 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 747,168 KB |
最終ジャッジ日時 | 2024-11-16 17:40:10 |
合計ジャッジ時間 | 67,432 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 5 TLE * 13 MLE * 21 |
ソースコード
import heapqn, m, p = map(int, input().split())a = list(map(int, input().split()))costs = [1] * nfor i in range(len(a)):while a[i] % p == 0:a[i] //= pcosts[i] += 1if all([ai == 1 for ai in a]):print(-1)exit()def create_edges(a, costs):dic = {}INF = 1000000000for i in range(len(a)):if dic.get(a[i], INF) > costs[i]:dic[a[i]] = costs[i]a = []costs = []for key in dic.keys():a.append(key)costs.append(dic[key])return a, costsdef dijkstra(a, costs, m):distances = { 1 : 0 }queue = [(0, 1)]heapq.heapify(queue)INF = 1000000000while len(queue) > 0:c, v = heapq.heappop(queue)if c > distances.get(v, INF):continueelif v > m:return cfor i in range(len(a)):nxt = v * a[i]cst = c + costs[i]if cst < distances.get(nxt, INF):distances[nxt] = cstheapq.heappush(queue, (cst, nxt))return INFa, costs = create_edges(a, costs)print(dijkstra(a, costs, m))