結果

問題 No.1284 Flip Game
ユーザー lam6er
提出日時 2025-04-16 16:50:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,136 ms / 2,000 ms
コード長 1,266 bytes
コンパイル時間 499 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 125,500 KB
最終ジャッジ日時 2025-04-16 16:52:10
合計ジャッジ時間 8,772 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    n = int(input())
    c = [list(map(int, input().split())) for _ in range(n)]
    
    heap = []
    dist = {}
    goal = (1 << n) - 1
    
    for s0 in range(n):
        state = (s0, 0, 1 << s0)
        dist[state] = 0
        heapq.heappush(heap, (0, s0, 0, 1 << s0))
    
    while heap:
        cost, last_p, B_mask, A_flips = heapq.heappop(heap)
        
        if (B_mask ^ A_flips) == goal:
            print(cost)
            return
        
        if cost > dist.get((last_p, B_mask, A_flips), float('inf')):
            continue
        
        current_white = B_mask ^ A_flips
        for q in range(n):
            if not (current_white & (1 << q)):
                new_A_flips = A_flips ^ (1 << q)
                if (B_mask & (1 << last_p)) == 0:
                    new_B_mask = B_mask | (1 << last_p)
                else:
                    new_B_mask = B_mask
                new_cost = cost + c[last_p][q]
                new_state = (q, new_B_mask, new_A_flips)
                if new_cost < dist.get(new_state, float('inf')):
                    dist[new_state] = new_cost
                    heapq.heappush(heap, (new_cost, q, new_B_mask, new_A_flips))
    
    print(-1)

if __name__ == "__main__":
    main()
0