ABC191 E - Come Back Quickly

1 min read読了の目安(約300字

問題概要

全ての頂点についてiについて、iから出発し一本以上の辺を通って元の頂点に戻ってくるときの最短距離を求めよ

解法

少し変わったダイクストラで解くことができる
普通のダイクストラでは、スタート地点の最短距離を0に初期化し、
スタート地点から開始して目的地の最短距離を求めるというようなことをする
今回の場合、スタート地点に隣接した頂点の全体から開始して、スタート地点の最短距離を求める
このとき、隣接した頂点の最短距離はスタート地点から貼られた辺の重みで初期化する(多重辺を含むため、その中で最小のものになる)
全点に対して、このようにダイクストラを使うことで答えを求めることができる

提出コード

https://atcoder.jp/contests/abc191/submissions/20213176