都市を頂点、道路を辺としたグラフの問題として考えます。

クエリを逆から処理することで、辺削除クエリのかわりに辺追加クエリがあるとみなせます。

辺追加クエリがなければワーシャルフロイド法による \(O(N^3)\) の前計算の下、クエリに \(O(1)\) で答えることができます。

辺追加クエリの処理を考えます。頂点 \(u\) から頂点 \(v\) への辺が追加されたとき、頂点 \(x\) から頂点 \(y\) への最短経路は、新たに追加された辺を通るか通らないかによって

• 元と変わらない
• \(x\) から \(u\) への最短経路、\(u\) から \(v\)、\(v\) から \(y\) への最短経路、をこの順に繋げたもの
• \(x\) から \(v\) への最短経路、\(v\) から \(u\)、\(u\) から \(y\) への最短経路、をこの順に繋げたもの

のいずれかになります。よって、元々の全頂点間最短距離がわかっていればこれは \(O(1)\) で求めることができ、全頂点間最短距離を \(O(N^2)\) で更新できます。

以上より、辺削除クエリの回数を \(T\) として、\(O(N^3+TN^2+Q)\) でこの問題を解くことができました。