ABC191 E Come Back Quickly

$ N頂点それぞれから試していっても間に合う.

ここでダイクストラ法を少し改変することを考える. 具体的には始点の距離の値を0ではなく無限大に初期化し, 遷移では0と仮定して再び戻すということを繰り返し, 途中途中で始点の最短距離を更新していくということをしていけばよい. このような操作を行ってもダイクストラ法は正常に動作する.

計算量は$ O(NMlogN)となる.