結果

問題 No.943 取り調べ
ユーザー Yukino DX.Yukino DX.
提出日時 2024-08-21 11:09:29
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 991 ms / 1,206 ms
コード長 1,311 bytes
コンパイル時間 29,762 ms
コンパイル使用メモリ 401,744 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-21 11:10:04
合計ジャッジ時間 19,486 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 0 ms
6,944 KB
testcase_04 AC 991 ms
6,944 KB
testcase_05 AC 554 ms
6,940 KB
testcase_06 AC 534 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 981 ms
6,944 KB
testcase_09 AC 139 ms
6,944 KB
testcase_10 AC 145 ms
6,940 KB
testcase_11 AC 71 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 168 ms
6,944 KB
testcase_18 AC 1 ms
6,944 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 187 ms
6,940 KB
testcase_23 AC 545 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::VecDeque;

use proconio::input;

fn main() {
    input! {
        n:usize,
        x:[[usize;n];n],
        a:[usize;n],
    }

    const INF: usize = std::usize::MAX;
    let mut ans = INF;
    for i in 0..1 << n {
        let mut g = vec![vec![]; n];
        let mut out = vec![0; n];
        for j in 0..n {
            for k in 0..n {
                if i & (1 << k) != 0 || x[j][k] == 0 {
                    continue;
                }

                g[k].push(j);
                out[j] += 1;
            }
        }

        if is_dag(n, &g, &mut out) {
            ans = ans.min(
                (0..n)
                    .map(|j| if i & (1 << j) != 0 { a[j] } else { 0 })
                    .sum::<usize>(),
            );
        }
    }

    println!("{}", ans);
}

fn is_dag(n: usize, g: &Vec<Vec<usize>>, out: &mut Vec<usize>) -> bool {
    let mut q = VecDeque::new();
    for i in 0..n {
        if out[i] == 0 {
            q.push_back(i);
        }
    }

    while let Some(crr) = q.pop_front() {
        for &nxt in g[crr].iter() {
            if out[nxt] == 0 {
                continue;
            }

            out[nxt] -= 1;
            if out[nxt] == 0 {
                q.push_back(nxt);
            }
        }
    }

    out.iter().all(|&out| out == 0)
}
0