🦔
ABC191 E - Come Back Quickly
問題概要
全ての頂点について
解法
少し変わったダイクストラで解くことができる
普通のダイクストラでは、スタート地点の最短距離を0に初期化し、
スタート地点から開始して目的地の最短距離を求めるというようなことをする
今回の場合、スタート地点に隣接した頂点の全体から開始して、スタート地点の最短距離を求める
このとき、隣接した頂点の最短距離はスタート地点から貼られた辺の重みで初期化する（多重辺を含むため、その中で最小のものになる）
全点に対して、このようにダイクストラを使うことで答えを求めることができる
提出コード
Discussion