問題
N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。
解法
最短路問題に帰着できる。
ダイクストラで解いているが、コストは1ずつしか増えないのでpriority_queueの代わりにqueueを使用している。
計算量
N個の街がひとつの輪となるようにつながっている。各街からは電車が出ており、それぞれの電車は最大range[i]個の街を移動できる。startからendまで行くのに必要な電車に乗る回数の最小値を求めよ。
最短路問題に帰着できる。
ダイクストラで解いているが、コストは1ずつしか増えないのでpriority_queueの代わりにqueueを使用している。