moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ UVa 問題 http://uva.onlinejudge.org/external/118/11813.html概要 無向グラフにおいて、グラフの接続情報とコストが与えられる。 全てのノードの内、店のノード番号が複数指定されるので、ノード0から出発して最小コストで全ての店を巡回せよ。制約 ノードとエッジの数はそれぞれ 100000 以下 店は10店舗以下。 解法 すべての店からダイクストラした後、TSPを解く。 高々11回(店舗数+はじめの位置)のダイクストラをすれば良い。 #include <iostream> #include <vector> #include <algorithm> #inc… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F20140526%2F1401064903" title="UVa11813 Shopping - Logfiles" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-05-26 09:41:43 rich https://logfiles.hatenablog.com/entry/20140526/1401064903 1.0 100%