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

bouzuya/tsukota で expo-router から react-navigation への移行を完了した。 react-navigation でも navigation が nest した状態がつらいのは同様だけど expo-router ほどではないという判断。

react-hook-form の isSubmitSuccessful は handleSubmit の引数に与えた callback がエラーなく終了した際に true になるけど、 handleSubmit の callback はエラーを返すべきでないとドキュメントに書かれており、いつ使うのか謎。

巡回セールスマン問題 (典型アルゴリズム問題集 C問題) https://atcoder.jp/contests/typical-algorithm/tasks/typical_algorithm_c
- https://atcoder.jp/contests/typical-algorithm/submissions/42275650
- DP
- ド典型の巡回セールスマン問題
- N <= 13 なので訪問済みの頂点を 2^13 までの bit 列で表現できる
- dp[i][j] := i に訪問済みで j に居るときの最小コスト とおく
- dp[1][0] = 0 , その他を INF を初期値にする
- 遷移は bit 列の 1 の少ない順に訪問すると良い、現在の頂点から訪問可能な箇所 (未訪問) のうちコストを更新できるものへ、 queue へ素朴に入れて取り出せばその順になる

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; n]; 1 << n];
    dp[1 << 0][0] = 0_usize;
    let mut deque = VecDeque::new();
    deque.push_back((1 << 0, 0_usize));
    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[set][u] + a[u][v];
            if new_cost < dp[new_set][v] {
                dp[new_set][v] = new_cost;
                deque.push_back((new_set, v));
            }
        }
    }
    let mut min = inf;
    for u in 1..n {
        min = min.min(dp[(1 << n) - 1][u] + a[u][0]);
    }
    let ans = min;
    println!("{}", ans);
}

今日のコミット。