結果

問題 No.3158 Collect Stamps
ユーザー akkey
提出日時 2025-05-24 11:53:56
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 917 bytes
コンパイル時間 26,328 ms
コンパイル使用メモリ 384,860 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-24 11:54:25
合計ジャッジ時間 17,472 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashSet;

use proconio::{input, marker::Usize1};
fn main() {
    input! {
        n: usize, m: usize, k: usize,
        a: [Usize1; k],
        t: [[usize; n]; n]
    }
    let mut visited = HashSet::new();
    let ans =
        (0..n).map(|x| dfs(x, n, &t, &a, m, 0, &mut visited))
        .min().unwrap();
    if let Some(ans) = ans {
        println!("{}", ans);
    } else {
        println!("-1");
    }
}
fn dfs(x: usize, n: usize, t: &[Vec<usize>], a: &[usize], m: usize, c: usize, visited: &mut HashSet<usize>) -> Option<usize> {
    if !visited.insert(x) {
        return None;
    }
    if visited.len() == m {
        visited.remove(&x);
        return Some(c + a.iter().copied().map(|a| t[x][a]).min().unwrap());
    }
    let ans =
        (0..n)
        .filter(|&i| i != x)
        .filter_map(|i| dfs(i, n, t, a, m, c + t[x][i], visited)).min();
    visited.remove(&x);
    ans
}
0