結果
| 問題 |
No.943 取り調べ
|
| コンテスト | |
| ユーザー |
ntuda
|
| 提出日時 | 2025-09-28 17:14:13 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 738 bytes |
| コンパイル時間 | 4,266 ms |
| コンパイル使用メモリ | 81,796 KB |
| 実行使用メモリ | 76,856 KB |
| 最終ジャッジ日時 | 2025-09-28 17:14:22 |
| 合計ジャッジ時間 | 5,319 ms |
|
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 13 WA * 11 |
ソースコード
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[i].append(j)
D0[i] += 1
def dfs():
D = D0[:]
while Q:
x = Q.pop()
D[x] = 0
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 = []
tmp = 0
for j in range(N):
if x & 1:
Q.append(j)
tmp += A[j]
x >>= 1
if dfs():
ans = min(ans,tmp)
print(ans)
ntuda