blog.bouzuya.net

2023-04-28 典型アルゴリズム問題集 C問題 を解いた

  • 巡回セールスマン問題 (典型アルゴリズム問題集 C問題) https://atcoder.jp/contests/typical-algorithm/tasks/typical_algorithm_c
    • https://atcoder.jp/contests/typical-algorithm/submissions/40999540
    • マスク後の値の比較で x != 0 とすべきところを x == 1 としてしまい 2WA
    • bitDP で解ける巡回セールスマン問題
    • dp[i][j] := i に居て j を巡回済みのときの最小コスト とおく
    • dp[0][1] = 0 を初期値として 0 から遷移可能な場所を幅優先探索の形で遷移する
    • 最小コストを更新できた場合のみ push_back していく
    • dp[i][(1 << n) - 1] + a[i][0] のうち、最小のものが答えになる
use std::collections::VecDeque;

use proconio::input;

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

    let inf = 1_usize << 60;
    let mut dp = vec![vec![inf; 1 << n]; n];
    dp[0][1] = 0_usize;
    let mut deque = VecDeque::new();
    deque.push_back((1, 0));
    while let Some((set, u)) = deque.pop_front() {
        for v in 0..n {
            if (set & (1 << v)) != 0 {
                continue;
            }
            let new_set = set | (1 << v);
            let new_cost = dp[u][set] + a[u][v];
            if new_cost < dp[v][new_set] {
                dp[v][new_set] = new_cost;
                deque.push_back((new_set, v));
            }
        }
    }
    let ans = (0..n).map(|i| dp[i][(1 << n) - 1] + a[i][0]).min().unwrap();
    println!("{}", ans);
}

今日のコミット。