ABC035 D トレジャーハント
滞在する町は一つに決め, 集中的に滞在するのが最適である. よってある町について最大何分滞在できるかが求まればよい. これは$ 1番目の町から$ i番目の町への最短距離を$ cost_i, $ i番目の町から$ 1番目の町への最短距離を$ cost2_iとすると, $ max(0, T - cost_i - cost2_i)分となる. $ cost_iについては前計算によって$ O(M \log N)で求められるが, $ cost2_iについては各町について調べると$ O(NM \log N)となって間に合わない. そこで逆辺を張ったグラフを考えると, これについても頂点$ 1のみについて見ればよく$ O(M \log N)で前計算できる. よってこの問題を$ O(max(N, M \log N))で解くことができた.