Developing Cities

解説

様々な解法がありますが、ここでは Writer 解について述べます。

まず道路の扱いですが、同じ二つの街同士を結ぶ道路に対しては最短距離のもののみを用いた方が有利であることは自明なので、 受け取った道路は最短距離のもののみを考えます。
すると、各街同士に最大 $1$ 本までしか道路は存在しないと見なせるので、道路の数は $O(N^2)$ となります。
よって、 Dijkstra 法を用いることで $O(QN^2 \log N)$ 、または $O(QN^2)$ で解くことが出来ます。

---

以下は計算量に $\log N$ が付かない処理の説明です。
なお、以下で用いる「辺」は「道路」を、「頂点」は「街」を指しています。

一般的に Dijkstra 法を用いる場合は高速化のために優先度付きキューで $O(E \log V)$ で処理するかと思います。 もちろん本問題も優先度付きキューを用いて処理してもらっても高速な言語であれば十分高速に処理できます。 二頂点間の辺は高々 $1$ 本として扱っているので辺の数は $O(N^2)$ となり、計算量は $O(N^2 \log N)$ となります。

優先度付きキューを用いない方法を考えてみましょう。
$N$ 個の頂点からまだ最短距離が確定していない最小コストの頂点を求めるのに $O(N)$ 、 遷移に $O(N)$ 、これを $N$ 回繰り返すので全体として $O(N^2)$ となります。
本問題では $\log N \lt 6$ なので、大きくは変わらないように感じるかもしれませんが、優先度付きキュー自体の定数倍などを考慮すると優先度付きキューを用いない方がより高速に処理できます。
このように、辺の上限が頂点数に対して大きい場合は計算量がより良いアルゴリズムが普段の制約のときと異なる場合があります。

以上より、全体として $O(QN^2)$ で解くことが出来ました。

実装例 ( $O(QN^2)$ 解法 )