結果
問題 |
No.943 取り調べ
|
ユーザー |
![]() |
提出日時 | 2023-12-11 10:36:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 699 ms / 1,206 ms |
コード長 | 625 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 77,944 KB |
最終ジャッジ日時 | 2024-09-27 04:24:26 |
合計ジャッジ時間 | 5,319 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
N = int(input()) X = [list(map(int,input().split())) for i in range(N)] A = list(map(int,input().split())) INF = 1 << 60 dp = [INF] * (1 << N) dp[0] = 0 for status in range(1 << N): for target in range(N): if (status >> target) & 1: continue cost = 0 for i in range(N): if (X[target][i] == 1) and (status >> i) & 1 == 0: # 頼りにしている人が自白していない cost = A[target] # うそをつく必要がある next_status = status | (1 << target) dp[next_status] = min(dp[next_status], dp[status] + cost) print(dp[-1])