Educational Codeforces Round 102 (Rated for Div. 2) - E. Minimum Path
解説
問題文をまず言い換えます。
をするということはその辺のコストを
にすることで、
をすることはその辺を2倍することと言い換えることができます。
そして、じゃない辺でやると得をしないので、任意の辺でどこのコストを0にしてどこのコストを2倍するかを決めてしまえばいいです。
ここまでくると後は簡単で、コスト0の辺を選んだかどうかとコストを倍にした辺を選んだかどうかを状態に持った拡張dijkstraをするとこの問題をとくことができました
