ABC204 E Rush Hour 2
まず, 通常のダイクストラ法のように, 各辺についてその場の最善(その辺を通る時間を短くすること)を選ぶ方が全体としても得である(貪欲). ここで, 最小化すべきものは道路$ iの通行を始める時刻を$ tとして, $ t + \lfloor \frac{D_i}{t + 1} \rfloor + C_iである. 定数であるので$ C_iの部分は考えなくてよく, $ t + \lfloor \frac{D_i}{t + 1} \rfloorを$ tの値を適切に定めて($ tは整数, 現在時刻より大きくなければならない)最小化すればよい. これは手元で実験すると$ \lfloor \sqrt D_i \rfloor付近の値を5個程度試せばよいということがわかる(実際, 相加相乗平均の関係を用いて示すことができる). よってこの問題を$ O(M \log N)で解くことができた.