No.035 C

まずはすべての2点間の距離を Floyd Warshal で求め, $S$ の初期値を計算する.

ここで, 道 $(X, Y, Z)$ を追加すると2点 $(A, B)$ 間の最短距離がどうなるかを考える.

もし新たに追加した道が $(A, B)$ 間の最短距離となるルート上に乗るならば, $A - X - Y - B$ または $A - Y - X - B$ というルートになるはずである.

したがって,

$$D(A, B) \leftarrow \min(D(A, B), D(A, X) + D(B, Y) + Z, D(A, Y) + D(B, X) + Z)$$

という式で新たな $D(A, B)$ を求めることができる.

なお, $S$ は int の範囲を超える可能性があるので注意する.