JOI 16本選 C 鉄道運賃(難易度8)
まず, クエリを先読みし, 各辺のコストがいつ増加するかを求めておく.
すると, BFSを工夫することによりこの問題を解くことができる.
具体的には, 最短距離の更新を先に行い, そのあとに向かう頂点が不満を抱く時刻を求めればよい.
以上より, この問題を
$ O(N + M)
で解くことができた.
実装例:
https://atcoder.jp/contests/joi2016ho/submissions/25339435
色々な解法があるが, これが一番シンプルかな. クエリ先読み + BFSという典型の組み合わせ.