Exactly K Steps 2 の解説

ダブリング的なことを考えた。

dp[bit][i][j] := ちょうど2^bit回の移動でi=>jした時の最小コスト

として定義する。

これの遷移は ワーシャルフロイド的にで以下のkを全探索すればOK

dp[bit - 1][i][k] + dp[bit - 1][k][j]

これが計算できればあとはkのbitごとに考えれば答え。

fn main() {
    input! {
        n: usize, k: usize,
        c: [[usize; n]; n]
    }
    let bit = 30;
    let mut dp = vec![vec![vec![usize::MAX; n]; n]; bit];
    for i in 0..n {
        for j in 0..n {
            dp[0][i][j] = c[i][j];
        }
    }
    for i in 0..bit - 1 {
        for j in 0..n {
            for k in 0..n {
                for mid in 0..n {
                    let left = dp[i][j][mid];
                    let right = dp[i][mid][k];
                    dp[i + 1][j][k].chmin(left + right);
                }
            }
        }
    }
    for v in 0..n {
        let mut que = VecDeque::new();
        que.push_back(v);
        let mut dist = vec![usize::MAX; n];
        dist[v] = 0;
        for b in 0..bit {
            if (k >> b) & 1 == 0 {
                continue;
            }
            let mut next = vec![usize::MAX; n];
            for i in 0..n {
                if dist[i] == usize::MAX {
                    continue;
                }
                for j in 0..n {
                    let pre = dist[i];
                    let d = dp[b][i][j];
                    next[j].chmin(pre + d);
                }
            }
            swap(&mut dist, &mut next);
        }
        println!("{}", dist[v]);
    }
}