きままにものづくり

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

ARC025 C問題

問題


C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder

解法

目的地を固定し、ダイクストラで最短経路を計算する。カメの距離d_T、ウサギの距離d_R d_T < d_Rとなる点の数を二分探索で計算する。

計算量

O(NM log N)
ダイクストラ: O(M log N)

コード