結果
問題 |
No.943 取り調べ
|
ユーザー |
![]() |
提出日時 | 2025-09-28 17:31:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 595 ms / 1,206 ms |
コード長 | 855 bytes |
コンパイル時間 | 479 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 77,120 KB |
最終ジャッジ日時 | 2025-09-28 17:31:40 |
合計ジャッジ時間 | 5,052 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
N = int(input()) X = [list(map(int,input().split())) for _ in range(N)] A = list(map(int,input().split())) E = [[] for _ in range(N)] D0 = [0] * N for i in range(N): for j in range(N): if X[i][j] == 1: E[j].append(i) D0[i] += 1 Q0 = [] for i in range(N): if D0[i] == 0: Q0.append(i) QS0 = set(Q0) def dfs(): D = D0[:] for q in Q: D[q] = 0 while Q: x = Q.pop() for y in E[x]: if D[y] == 0: continue D[y] -= 1 if D[y] == 0: Q.append(y) return sum(D) == 0 ans = sum(A) for i in range(1<<N): x = i Q = Q0[:] tmp = 0 for j in range(N): if j not in QS0 and x & 1: Q.append(j) tmp += A[j] x >>= 1 if dfs(): ans = min(ans,tmp) print(ans)