結果

問題 No.1284 Flip Game
ユーザー lam6er
提出日時 2025-04-16 01:13:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,917 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 131,760 KB
最終ジャッジ日時 2025-04-16 01:15:11
合計ジャッジ時間 10,441 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    c = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        c.append(row)
        idx += N
    
    target = (1 << N) - 1
    heap = []
    INF = float('inf')
    distance = {}
    
    for s in range(1, N+1):
        w_mask = 1 << (s-1)
        b_mask = 0
        state = (s, w_mask, b_mask)
        distance[state] = 0
        heapq.heappush(heap, (0, s, w_mask, b_mask))
    
    min_cost = INF
    
    while heap:
        cost, current_p, w_mask, b_mask = heapq.heappop(heap)
        state_key = (current_p, w_mask, b_mask)
        if cost > distance.get(state_key, INF):
            continue
        if w_mask == target:
            if (b_mask & (1 << (current_p - 1))) != 0:
                if cost < min_cost:
                    min_cost = cost
            continue
        for q in range(1, N+1):
            if (w_mask & (1 << (q-1))) != 0:
                continue
            new_cost = cost + c[current_p-1][q-1]
            new_w_mask_A = w_mask | (1 << (q-1))
            if new_w_mask_A == target:
                if (b_mask & (1 << (current_p - 1))) != 0:
                    if new_cost < min_cost:
                        min_cost = new_cost
                continue
            if (b_mask & (1 << (current_p - 1))) == 0:
                new_w_mask = new_w_mask_A & ~(1 << (current_p - 1))
                new_b_mask = b_mask | (1 << (current_p - 1))
            else:
                new_w_mask = new_w_mask_A
                new_b_mask = b_mask
            new_state = (q, new_w_mask, new_b_mask)
            if new_cost < distance.get(new_state, INF):
                distance[new_state] = new_cost
                heapq.heappush(heap, (new_cost, q, new_w_mask, new_b_mask))
    
    print(min_cost)

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