貪欲法によるTSP (paizaランク A 相当)

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。

ここでは、巡回セールスマン問題に対する貪欲法を学習しましょう。このアルゴリズムは発見的解法 (ヒューリスティクス) と呼ばれるもので、ある程度良い解が出力されることが期待されるものの、解の精度は全く保証されません。

巡回セールスマン問題に対する貪欲法の概要は、以下の通りです。

・ 都市を頂点とし、辺を 1 本も含まないグラフ G を用意する
・ 都市のペアを結ぶ辺を全て列挙し、E とする
・ E が空になるまで、以下を繰り返す
    ・ E に含まれる辺のうち最も長さが短いものを E から削除して e とする
    ・ G に e を追加したグラフを G' とする。G' のすべての頂点の次数が 2 以下かつ G' に閉路が存在しないなら、G を G' で更新する
・ この時点で G は全都市を結ぶ一本のパスになっている (次数 1 の都市がただ 2 つ存在する) ため、その始点と終点を辺で繋いで巡回路を作る

n 個の都市のデータ (都市 0、都市 1、...、都市 n-1) が与えられます。この貪欲法を実装し、巡回路を求めてください。なお、各都市は二次元平面上の点として与えられ、都市間の距離にはユークリッド距離を用いるものとします。

ただし、ジャッジの都合上、辺 e の選び方は以下のようにしてください。

・ E に含まれる辺のうち最も長さが短いものを E から削除して e とする。ただし、最も長さが短い辺が複数存在する場合は、以下の優先順序に従って e を選択する。
    ・ 辺 (a, b) と 辺 (c, d) (ただし a < b、 c < d) について
        ・ a < c または (a == c かつ b < d) ならば、辺 (a, b) を先に選択する
        ・ a > c または (a == c かつ b > d) ならば、辺 (c, d) を先に選択する

この制約により、貪欲法による解 (巡回路) は一意に定まります。

巡回路を出力する際、どの都市を始点とするかは自由です。例えば、入力例において、

3
1
2
0

や

1
3
0
2

などは正解と判定されます。一方で、

0
1
2
3

や

1
3
2
0

などは巡回路が正しくないため誤答と判定されます。