ARC025 C - ウサギとカメ

問題：C - ウサギとカメ

解答：Submission #13491153 - AtCoder Regular Contest 025

解法：N ≦ 2500、M ≦ 3000 なので全点ダイクストラやっても間に合いそう。(TLEも7秒)

目的地を固定して、目的地を始点とするダイクストラをする。すると目的地から各中継点への最短距離が分かる。これを配列gに格納する。
さらにカメのスタート地点lefを固定して、g[lef] / t < g[rig] / r、すなわちr * g[lef] < t * g[rig] なるウサギのスタート地点rigの個数を求める。
これは、gをソートして尺取り法で求めることができる。

要注意なのは、カメがウサギより速い場合は、rig < lef となる場合があり、その際lef = rigをとれないため、rigの個数はn - rig - 1となる。（これに気づかず自力ACならず…）