babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング yukicoder レベル 2.5 問題 問題 解法 解答 問題 yukicoder.me 解法 ツーリストチケットはツアーの中で１回しか使えないので，行きか帰りかのどちらかで使うことになる．なので，頂点 1 から各頂点へツーリストチケットを使って行くときの最小コストと，使わないで行くときの最小コストをそれぞれ２つ求め，この２つを足し合わせたものが各頂点の答えになる．これは，Dijkstra 法を用いて求められるが，前者の最小コストを求める際には工夫が必要になる．具体的には，ある頂点に達するまでにツーリストチケットを使ったかどうかを状態として頂点番号やコストと一緒に持つ必要がある．O(NlogM)． 解答 yukicoder.me 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F03%2F22%2F232044" title="yukicoder：No.807 umg tours - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20190322/20190322223642.png Hatena Blog https://hatena.blog 2019-03-22 23:20:44 rich https://babcs2035.hateblo.jp/entry/2019/03/22/232044 1.0 100%