CodeEval 219 the Tourist

問題文：https://www.codeeval.com/browse/219/

概要

  • 探偵が複数の都市を全て回るとき、その距離の合計値の最小を出力する問題。
  • こう書くと、巡回セールスマン問題だと思いたいですが、なんと、 最小全域木 問題である。やばくないですか。問題文ではHeと 単数形 で書かれていますが…分身できるんですか。
  • 普通にクラスカル法で解けば良いのでその部分の解説は他に譲ります。もしくは私の解答集を見ても。

注意点

  • Falseを出力すべきなのは、
    • グラフが連結でない場合
    • グラフに示されていない点が存在する場合
  • である。たとえば、1 2 1 | 2 4 1の答えは、2ではなくFalseである。つまり、点番号を詰める必要はないということ。
  • 多重辺を持つ場合、 一番後ろの辺を採用 する。例えば、1 2 1 | 2 1 2の場合、点1と点2の間にコスト2の無向辺を張る。

まとめ