いろはちゃんコンテスト Day1：I - リスのお仕事

問題

atcoder.jp

解法

木を頂点，枝を辺として無向グラフを考える．このとき，前に移動した枝の隙間の大きさを状態として加えたダイクストラ法を用いて，頂点 1 から各頂点まで休まなければいけない最小の回数が求まる．よって，答えは (dist[N] + 1) * K となる．

解答

atcoder.jp