この問題を線形時間で解く方法を紹介します。

まず、クエリを逆順に見ることで、辺が少しずつ増えていく問題になります。

この時、各都市について最初に発電所から辿れるようになる時間を求めれば良く、これは最短距離問題として解くことができます。

具体的には、各辺に対してその重みを電線が新たに貼られる時刻と定めれば、その \((\min, \max)\) 閉半環が成す最短距離が答えとなります。

普通にDijkstra法を用いると計算量は \(O(E+(N+M)\log(N+M))\) ですが、最短距離としてあり得る値は \(0, 1, \ldots, Q\) だけであることを利用するとDial’s Algorithmなどで \(O(N+M+E)\) で解くことができます。

なお、発電所が複数ある問題ですが、このように始点が複数ある場合は超頂点を一つ用意してそこから各発電所に繋げることで始点を一つにできます。