betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング Problem - D - Codeforces 計算量がキツキツなので想定解じゃないような気もするのですが、通せたので私の解法を書きます。 問題概要 頂点の有向完全グラフが与えられ、各辺にコストが設定されている。 頂点1からスタートしてちょうど 辺を通って頂点1に戻る経路であって、奇閉路を含まないものの最小コストを求めよ。頂点、辺は同じものを何度でも通って良い。 制約 であって は偶数 解法 が最も大きい のケースにおいて、経路は以下のようになっています。（実際には頂点や辺が重複していることがあります） この図で青く塗っている、始点/終点以外の偶数ステップ目で訪れる頂点は高々4個です。これを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F02%2F24%2F151724" title="Codeforces Round #623 (Div. 1) D. Tourism - ARMERIA" 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/betrue12/20200224/20200224145146.png Hatena Blog https://hatena.blog 2020-02-24 15:17:24 rich https://betrue12.hateblo.jp/entry/2020/02/24/151724 1.0 100%