ABC191 E - Come Back Quickly - kanten4205’s diary

　ピースピース　競技プログラミングのネタ枠担当　Kantenちゃんだぞ～　

　ABC191 E - Come Back Quickly の解法が解説と違ったので、メモ書き程度に記しておきます。

問題

　これです

解法

　ダイクストラ法を走らせるのは解説と一緒です。しかし、各頂点 $i (1 \leq i \leq N)$ を始点としてダイクストラ法を走らせるとき、普段は探索前に、始点から頂点 $j (1 \leq j \leq N)$ への距離を $dist[j]$ とおいて、 $dist[i]=0$ と初期化するのですが、今回はこれを行いません。そして、ループが1回目のときは、どうせ $dist[j]$ の値は、2頂点 $i, j$ を結ぶ辺の重さですから、この値に、 $dist[j]$ を更新してやります。2回目以降のループは、普段通りのループと変わりません。そして、探索後に、 $dist[i]$ の値が INF だったら -1 、そうでなければ $dist[i]$ の値を出力すればよいです。たぶん計算量は解説と一緒だと思います（雑）。

提出コード

atcoder.jp

以上　Kanten ちゃんでした～　じゃあねー！★