結果

問題 No.1284 Flip Game
コンテスト
ユーザー lam6er
提出日時 2025-04-16 01:10:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,225 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 81,380 KB
実行使用メモリ 122,296 KB
最終ジャッジ日時 2025-04-16 01:11:50
合計ジャッジ時間 7,419 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    N = int(input())
    c = []
    for _ in range(N):
        row = list(map(int, input().split()))
        c.append(row)
    
    full_mask = (1 << N) - 1
    heap = []
    dist = dict()
    
    # Initialize with all possible starting positions (q0)
    for q0 in range(N):
        initial_mask = 1 << q0
        initial_used = 0
        state = (q0, initial_used, initial_mask)
        dist[state] = 0
        heapq.heappush(heap, (0, q0, initial_used, initial_mask))
    
    answer = None
    
    while heap:
        current_cost, last_p, used_mask, current_mask = heapq.heappop(heap)
        
        # Skip if a lower cost path to this state has already been found
        if dist.get((last_p, used_mask, current_mask), float('inf')) < current_cost:
            continue
        
        # Explore all possible next moves
        for q in range(N):
            if (current_mask & (1 << q)) == 0:  # Check if q is red
                mask_after_A = current_mask ^ (1 << q)
                cost_increment = c[last_p][q]
                new_cost = current_cost + cost_increment
                
                # Check if this transition leads to termination
                if mask_after_A == full_mask:
                    if (used_mask & (1 << last_p)):
                        # Found the minimal cost
                        print(new_cost)
                        return
                
                # Proceed with B's action
                if not (used_mask & (1 << last_p)):
                    mask_after_B = mask_after_A ^ (1 << last_p)
                    new_used_mask = used_mask | (1 << last_p)
                else:
                    mask_after_B = mask_after_A
                    new_used_mask = used_mask
                
                new_last_p = q
                new_state = (new_last_p, new_used_mask, mask_after_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, new_last_p, new_used_mask, mask_after_B))
    
    print(answer)

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