結果
問題 |
No.2039 Copy and Avoid
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:02:28 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,236 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 283,484 KB |
最終ジャッジ日時 | 2025-06-12 20:07:45 |
合計ジャッジ時間 | 6,701 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 30 |
ソースコード
import heapq def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx += 1 M = int(input[idx]); idx += 1 A = int(input[idx]); idx += 1 B = int(input[idx]); idx += 1 forbidden = set(map(int, input[idx:idx+M])) heap = [] heapq.heappush(heap, (0, 1, 1)) visited = {} while heap: cost, x, y = heapq.heappop(heap) if x in forbidden: continue if x == N: print(cost) return if (x, y) in visited: if visited[(x, y)] <= cost: continue visited[(x, y)] = cost # Process operation a new_x = x + y if new_x == N: print(cost + A) return if new_x < N and new_x not in forbidden: if (new_x, y) not in visited or cost + A < visited.get((new_x, y), float('inf')): heapq.heappush(heap, (cost + A, new_x, y)) # Process operation b new_y = x if (x, new_y) not in visited or cost + B < visited.get((x, new_y), float('inf')): heapq.heappush(heap, (cost + B, x, new_y)) print(-1) if __name__ == '__main__': main()