2026-10-14
all_pairs.rs
fn all_pairs(d: &mut [Vec<Option<u32>>]) {
}
d は、n 個の頂点(vertex)を結ぶ向き付きの辺(edge)の長さの表で、d[i][j] は頂点 i から j へ直接向かう辺の長さを Some で、辺がなければ None で持ちます。d[i][i] はどれも Some(0) です。i から辺を向きに沿ってたどり j に着く道筋を i から j への経路といい、通った辺の長さの和をその経路の長さといいます。d の各要素を、i から j への経路の長さの最小値に書き換える all_pairs を書いてください。経路がなければ None のままにします。辺の長さの和は u32 に収まるものとし、d が空なら何もしません。入力例は呼ぶ前の d を、出力例は呼んだあとの d を {:?} で表示したものです。
入力例 1
[[Some(0), Some(4), None], [None, Some(0), Some(1)], [Some(2), None, Some(0)]]
出力例 1
[[Some(0), Some(4), Some(5)], [Some(3), Some(0), Some(1)], [Some(2), Some(6), Some(0)]]
入力例 2
[[Some(0), Some(7)], [None, Some(0)]]
出力例 2
[[Some(0), Some(7)], [None, Some(0)]]
入力例 3
[]
出力例 3
[]
Reference
fn all_pairs(d: &mut [Vec<Option<u32>>]) {
let n = d.len();
for k in 0..n {
for i in 0..n {
for j in 0..n {
let via = d[i][k].zip(d[k][j]).map(|(a, b)| a + b);
d[i][j] = d[i][j].into_iter().chain(via).min();
}
}
}
}
要になるのは、k のループをいちばん外に置くことです。k 回目の繰り返しでは、頂点 k を途中で通る経路の長さ d[i][k] + d[k][j] を、それまでの d[i][j] と比べます。k 回目を終えた時点の d[i][j] は、途中で通る頂点を0から k までに限ったときの最短の長さになり、最後の k を終えると、どの頂点を通ってもよい最短の長さになります1。この方法をワーシャル・フロイド法(Floyd-Warshall algorithm)といいます。k を内側に置くと各 (i, j) を1回しか更新せず、あとで短くなった値を使えないので、辺を何本も通る経路を見落とすことがあります。
辺がないことを None で表すので、和と最小値の取り方にも注意が要ります。via は、zip で両方が Some のときだけ和を作り、どちらかが None なら None になります。d[i][j].min(via) と書きたくなりますが、Option の順序では None がどの Some よりも小さいので、経路のない側が勝ってしまいます。into_iter().chain(via) は2つの Option を、要素が0〜2個の並びとしてつなぎ、min() は Some の中身だけから最小値を選びます。両方とも None なら、並びが空なので None が返ります。
掲載したのは参考実装で、唯一の正解ではありません。match で4通りの組み合わせを書き分けても同じ結果になります。
k回目の間、d[i][k]とd[k][j]は書き換わりません。d[k][k]がSome(0)なので、kを通る経路を足しても短くならないからです。そのため同じ表を書き換えながら進めても、前の回の値で計算したのと同じ結果になります。