Electro-Communication

この問題は $N + 1 \leq i \leq N + M$ について、 頂点 $i$ を始点としたダイクストラ法を行い、それぞれの頂点 $j \: (1 \leq j \leq N)$ について最小の時間を求めればよいことが分かります。

しかし、愚直に行うと $O( MK \log (N + M))$ の計算量がかかってしまい、実行制限時間に間に合いません。

ここで、仮想頂点 $S$ を用意し、頂点 $S$ と それぞれの $i$ についてコスト $0$ の辺を張ることによって、$1$ 回のダイクストラ法で全ての頂点に対する最小の時間を求めることができます。

計算量は $O(K \log (N + M)$ で十分高速です。