結果

問題 No.943 取り調べ
ユーザー Yukino DX.
提出日時 2024-08-21 11:09:29
言語 Rust
(1.83.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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