joi2016ho C - 鉄道運賃 (Train Fare)（難易度8）
https://gyazo.com/997e84e06e9afe2fc4f6718d371790ad
地獄
解説
小課題2まではクエリ毎に頂点1を始点としたダイクストラをすると、$ O(QM\log N)で出来る。
小課題3からは、いらない辺を減らすことで計算量を減らしていく。
まず、2円に値上がりした辺はもういらないので削除する。
また、頂点1からの最短距離に使われない有向辺は前もって削除する。
$ uと$ vを繋いでる無向辺があったとする。ここで頂点1から頂点$ u,vへの最短距離を$ d_u,d_vとすると、$ |d_u - d_v| \leq 1である。
証明
仮に$ d_u - d_v \geq 2だとすると、$ vから$ uに行くことで$ d_u - d_v \leq 1となるので矛盾。よって上の命題は成り立つ。
なので、全ての頂点について頂点1からの最短路を調べて有向辺を削除することができる。
すると、残った有向辺で構成されるグラフはDAGになる（DAGじゃないと永遠に最短経路が更新されるので）。