結果
問題 |
No.2039 Copy and Avoid
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:12:52 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,410 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,952 KB |
実行使用メモリ | 304,452 KB |
最終ジャッジ日時 | 2025-06-12 15:12:59 |
合計ジャッジ時間 | 6,735 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 30 |
ソースコード
import heapq def main(): import sys input = sys.stdin.read data = input().split() idx = 0 n = int(data[idx]) idx +=1 m = int(data[idx]) idx +=1 a = int(data[idx]) idx +=1 b = int(data[idx]) idx +=1 c = list(map(int, data[idx:idx+m])) forbidden = set(c) heap = [] heapq.heappush(heap, (0, 1, 1)) visited = dict() visited[(1, 1)] = 0 found = False answer = -1 while heap: cost, x, y = heapq.heappop(heap) if x == n: answer = cost found = True break if visited.get((x, y), float('inf')) < cost: continue # Operation a new_x_a = x + y if new_x_a not in forbidden: new_cost_a = cost + a key = (new_x_a, y) if key not in visited or new_cost_a < visited.get(key, float('inf')): visited[key] = new_cost_a heapq.heappush(heap, (new_cost_a, new_x_a, y)) # Operation b new_x_b = x new_y_b = x new_cost_b = cost + b key = (new_x_b, new_y_b) if key not in visited or new_cost_b < visited.get(key, float('inf')): visited[key] = new_cost_b heapq.heappush(heap, (new_cost_b, new_x_b, new_y_b)) print(answer if found else -1) if __name__ == "__main__": main()