結果
| 問題 |
No.943 取り調べ
|
| コンテスト | |
| ユーザー |
ntuda
|
| 提出日時 | 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)
ntuda