第二回全国統一プログラミング王決定戦予選 D - Shortest Path on a Line (600)
本番中の考察
愚直にやると辺が$ O(N^2M)になり到底間に合わない
必要コストは辺を経る毎に単調増加
最大限進んでここまでならこのコストというのをmapで持っておけば良さそう
実装に失敗
範囲内の辺を全部見るのに$ O(N)かかるので全体で$ O(NM)になりそう
天才的な解説を見て
L,R間で同じコストの辺を貼るのでLとRで辺を貼って、後ろに好きなだけコスト0で戻れるようにすると辺が減る
辺が$ O(N^2M)から$ O(N+M)に減ったのでダイクストラ法で1からの最短距離を求めれば良い
有向グラフとして解く