ARC035 C - アットコーダー王国の交通事情
解答:Submission #10395104 - AtCoder Regular Contest 035
解法:N ≦ 400で、N3 = 6.4 * 107なので数回ならワーシャルフロイドが可能。ただしクエリ全てでワーシャルフロイドはできない。
まずはワーシャルフロイドで最初に与えられたグラフの全点間最短距離を求める。
各クエリで更新される部分はx-yを使うパスになるため、頂点i, jについてi -> j に比べてi -> x -> y -> j もしくは i -> y -> x -> jの方が短くなる場合に最短距離が更新される。なので各クエリについて頂点i, jの全ての組について上記の更新を全て行えばよい。