結果

問題 No.2039 Copy and Avoid
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:07:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,236 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 81,896 KB
実行使用メモリ 257,660 KB
最終ジャッジ日時 2025-06-12 20:14:14
合計ジャッジ時間 6,787 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0