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