結果

問題 No.943 取り調べ
コンテスト
ユーザー Yukino DX.
提出日時 2024-08-21 11:09:29
言語 Rust
(1.99.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 607 ms / 1,206 ms
+ 6µs
コード長 1,311 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,603 ms
コンパイル使用メモリ 181,628 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-11-05 14:12:53
合計ジャッジ時間 9,664 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: use of deprecated constant `std::usize::MAX`: replaced by the `MAX` associated constant on this type
  --> src/main.rs:12:36
   |
12 |     const INF: usize = std::usize::MAX;
   |                                    ^^^
   |
   = note: `#[warn(deprecated)]` on by default

ソースコード

diff #
raw source code 

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