Educational Codeforces Round 38 D. Buy a Ticket

• 問題

問題概要

N頂点M辺の無向グラフと各辺の距離が与えられる.
また各頂点に対してコストc[i]が与えられる.
各i (1<=i<=N)に対し min_j(2dist(i, j)+c(j))を求めよ.
2 <= N <= 210⁵, 1 <= M <= 2*10⁵

解法

Dijkstraで各頂点とそのコストを初期位置としてキューに入れると,
各頂点に対し各(始点のコスト)+(始点からの距離)を更新していくので解ける.

メモ

始点複数のDijkstraを初めて見たのでできなかった. 言われて見ると,そうだね,という感じ.
オーダーがすごく見積もりにくい気がするのだけどまあO(E+Vlog(V))かな
こういうタイプは無向グラフには使えないので注意.
一回やってれば解けそう.

コード