街を頂点、道路などを辺とみなすことで、この問題はグラフの最短経路問題とみなせます。

道路と空港の追加がない問題

ワーシャルフロイド法によりあらかじめ全頂点対の最短距離を求めておくことで \(O(N^3+Q)\) で解けます。

道路のみ追加がある問題

ワーシャルフロイド法によりあらかじめ最初の時点での全頂点対の最短距離を求めておきます。

\(x,y\) を結ぶコスト \(t\) の辺が追加されたとき、頂点 \(i,j\) 間の最短経路は

• 変化しない
• \(i\) から \(x\) に行き、新たな辺を通って \(y\) へ、その後 \(j\) へ行く
• \(i\) から \(y\) に行き、新たな辺を通って \(x\) へ、その後 \(j\) へ行く

のいずれかです。これらは各 \((i,j)\) に対し \(\Theta(1)\) で計算できるため、全頂点対の最短距離の再計算を \(\Theta(N^2)\) で行うことができます。よって全体で \(O(N^3+N^2Q)\) 時間で解けます。

元の問題

空港がある街同士を直接結ぶと、最終的に全体で最大 \(\Theta(N^2)\) 本の航路がある状態に至ります。空港の追加ごとに空港がある街同士を直接結ぶ辺を追加して前節のように \(\Theta(N^2)\) かけて更新すると全体で \(\Theta(N^4+N^2Q)\) となり、実行時間制限に間に合わせるのは困難です。複数の辺をまとめて追加しワーシャルフロイドをやり直すとしても同様です。

そこで空港がある街同士を直接つなぐのではなく、「上空」を表す頂点を追加し、以下のように考えます。

• 空港のある街からは「上空」へ時間 \(T\) で移動可能
• 「上空」からは空港のある街へ時間 \(0\) で移動可能

これにより、新たな空港が作られた際に追加する辺は \(2\) 本となり、全頂点対の最短距離の再計算を \(\Theta(N^2)\) で行えるようになり、全体で \(O(N^3+N^2Q)\) 時間でこの問題が解けます。