結果

問題 No.1284 Flip Game
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:46:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,017 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 122,332 KB
最終ジャッジ日時 2025-03-31 17:46:34
合計ジャッジ時間 8,795 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    n = int(input())
    c = [list(map(int, input().split())) for _ in range(n)]
    
    heap = []
    dist = dict()
    
    # Initialize all possible starting points (step 0)
    for start in range(n):
        mask_white = 1 << start
        mask_b = 0
        state = (start, mask_white, mask_b)
        heapq.heappush(heap, (0, start, mask_white, mask_b))
        dist[state] = 0
    
    while heap:
        current_cost, prev_p, mask_white, mask_b = heapq.heappop(heap)
        
        # Check if we have already processed this state with a lower cost
        if dist.get((prev_p, mask_white, mask_b), float('inf')) < current_cost:
            continue
        
        # Generate all possible next moves by choosing a red card (not in mask_white)
        for q in range(n):
            if not (mask_white & (1 << q)):
                new_cost = current_cost + c[prev_p][q]
                new_mask_white_A = mask_white | (1 << q)
                
                # Check if B can flip the previous_p
                if (mask_b & (1 << prev_p)) == 0:
                    new_mask_white_B = new_mask_white_A ^ (1 << prev_p)
                    new_mask_b = mask_b | (1 << prev_p)
                else:
                    new_mask_white_B = new_mask_white_A
                    new_mask_b = mask_b
                
                # Check if this new state is the terminal state
                if new_mask_white_B == (1 << n) - 1 and new_mask_b == mask_b:
                    print(new_cost)
                    return
                
                new_state = (q, new_mask_white_B, new_mask_b)
                # Update the distance if this path is better
                if new_cost < dist.get(new_state, float('inf')):
                    dist[new_state] = new_cost
                    heapq.heappush(heap, (new_cost, q, new_mask_white_B, new_mask_b))
    
    # If not found (which shouldn't happen as per problem statement)
    print(-1)

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