問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。
ここでは、巡回路の長さ、巡回路長を計算してみましょう。
n 個の都市 (都市 1、都市 2、...、都市 n) のデータと、巡回路が与えられます。巡回路長を計算してください。なお、各都市は二次元平面上の点として与えられ、都市間の距離にはユークリッド距離を用いるものとします。
n
x_1 y_1
x_2 y_2
...
x_n y_n
p_1 p_2 ... p_n
都市 p_1 からスタートして p_2, ..., p_n の順に都市を巡り、最後に都市 p_1 に戻る巡回路の長さを出力してください。絶対誤差が 10^-6 以下なら正解と判定されます。
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 8
・ -1,000 ≦ x_i, y_i ≦ 1,000 (1 ≦ i ≦ n)
・ i ≠ j ならば (x_i, y_i) ≠ (x_j, y_j)
・ p は {1, 2, ... , n} を並べ替えた順列
3
0 0
1 0
0 1
1 2 3
3.414213562373