結果

問題 No.943 取り調べ
ユーザー lam6er
提出日時 2025-03-20 20:31:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 318 ms / 1,206 ms
コード長 1,611 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 82,628 KB
最終ジャッジ日時 2025-03-20 20:32:48
合計ジャッジ時間 3,254 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    
    X = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        idx +=N
        X.append(row)
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    
    # Precompute dependency masks
    deps_mask = [0] * N
    for i in range(N):
        for j in range(N):
            if X[i][j]:
                deps_mask[i] |= 1 << j
    
    # Precompute T(S) for all S
    precompute_T = [0] * (1 << N)
    for S in range(1 << N):
        T = 0
        while True:
            current = S | T
            new_T = T
            for i in range(N):
                if not (current & (1 << i)):
                    required = deps_mask[i]
                    if (current & required) == required:
                        new_T |= 1 << i
            if new_T == T:
                break
            T = new_T
        precompute_T[S] = T
    
    INF = float('inf')
    dp = [INF] * (1 << N)
    dp[0] = 0
    
    ans = INF
    for S in range(1 << N):
        if dp[S] == INF:
            continue
        T = precompute_T[S]
        current_cover = S | T
        if current_cover == (1 << N) - 1:
            ans = min(ans, dp[S])
            continue
        # Add each uncovered member
        for i in range(N):
            if not (current_cover & (1 << i)):
                next_S = S | (1 << i)
                if dp[next_S] > dp[S] + A[i]:
                    dp[next_S] = dp[S] + A[i]
    
    print(ans if ans != INF else 0)

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