AtCoder Beginner Contest 132：E - Hopscotch Addict

問題
解法
解答

問題

https://atcoder.jp/contests/abc132/tasks/abc132_e

解法

各頂点についてけんけんぱの k 歩目 (0 <= k <= 2) で到達するために辺を通る回数の最小値を求めることを考える．これは，各頂点について 3 つの状態（けんけんぱの歩数）をもっておき，ダイクストラ法を適用することで求めることができる．答えは頂点 T をけんけんぱの 0 歩目で到達するための最小のコストを 3 で割ったものになる．O(MlogN)．