Namaran

Code daily. Without assist.

2026-10-14

snapshot.rs

const INF: u32 = u32::MAX;

fn main() {
    let mut d = [
        [0, INF, 1, 9],
        [INF, 0, INF, 1],
        [INF, 1, 0, INF],
        [INF, INF, INF, 0],
    ];
    let base = d;
    for k in 0..4 {
        for row in d.iter_mut() {
            let ik = row[k];
            for (x, b) in row.iter_mut().zip(base[k]) {
                *x = (*x).min(ik.saturating_add(b));
            }
        }
    }
    println!("{}", d[0][3]);
}

このコードは、4つの頂点(vertex)を結ぶ向き付きの辺(edge)の長さの表 d を、頂点どうしの最短距離の表に書き換えるつもりのものです。d[i][j] は頂点 i から j へ直接向かう辺の長さで、辺がなければ INF です。頂点0から3へは 0→2→1→3 と進む長さ3の経路がありますが、実行すると、いまは d[0][3] として 9 が出力されます。本来の出力は 3 です。

Answer

Wrong

let base = d;
for k in 0..4 {
    for row in d.iter_mut() {
        let ik = row[k];
        for (x, b) in row.iter_mut().zip(base[k]) {

d の型 [[u32; 4]; 4] は Copy なので、let base = d; はループに入る前の表をまるごと写します。k を経由する長さは row[k] と base[k][j] の和で求めていますが、base[k] はいつまでも最初の辺の長さのままで、前の回で縮んだ d[k][j] が後の回に伝わりません。

k = 1 の回で、2→1→3 が見つかって d[2][3] は2に縮みます。ところが k = 2 の回に頂点0から2を経由する長さを求めるときに使われるのは、縮む前の base[2][3]、つまり INF です。0→2→1→3 の長さ3は見つからず、d[0][3] には直接の辺の9が残ります。

Right

for k in 0..4 {
    let base = d[k];
    for row in d.iter_mut() {
        let ik = row[k];
        for (x, b) in row.iter_mut().zip(base) {

各回の初めに、その時点の k 行目を写します。前の回までに縮んだ値が写しに入るので、k = 2 の回には d[2][3] の2が使われ、d[0][3] は3になります。k 回目の間、k 行目そのものは書き換わりません。d[k][k] が0なので、k を経由しても d[k][j] より短くならないからです。そのため回の途中で写しと本物の値がずれることもありません1。

  1. 写しを取るのは、d.iter_mut() で各行を書き換え用に借りている間、同じ d から d[k] を読むことを借用チェッカーが許さないからです。d[i][j] のように添字だけで書けば、写しは要りません。