きろく

特筆すべき記録のまとめ

yukicoder:No.807 umg tours

問題

yukicoder.me

解法

ツーリストチケットはツアーの中で1回しか使えないので,行きか帰りかのどちらかで使うことになる.なので,頂点 1 から各頂点へツーリストチケットを使って行くときの最小コストと,使わないで行くときの最小コストをそれぞれ2つ求め,この2つを足し合わせたものが各頂点の答えになる.これは,Dijkstra 法を用いて求められるが,前者の最小コストを求める際には工夫が必要になる.具体的には,ある頂点に達するまでにツーリストチケットを使ったかどうかを状態として頂点番号やコストと一緒に持つ必要がある.O(NlogM).

解答

yukicoder.me

f:id:babcs2035:20190322223642p:plain