きままにものづくり

日々の気付いたことなんかを書いてます。

SRM583Div1Easy

問題

N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。

解法

最短路問題に帰着できる。
ダイクストラで解いているが、コストは1ずつしか増えないのでpriority_queueの代わりにqueueを使用している。

計算量

 O(N)

コード