巡回セールスマン問題 (bitmask DP, 構築)
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
巡回セールスマン問題 (TSP) とは、辺にコストが付いたグラフが与えられたときに、コストの総和が最小になるようなハミルトン閉路を求める問題です。
有向グラフの各辺のコストを表す隣接行列が与えられるので、巡回セールスマン問題の解を求めてください。
今回は最小値だけでなく、コストの総和が最小になるようなハミルトン閉路を実際に 1 つ求めてください。
bitmask DP で実際に構築するには、前問での DP の更新の際に、どの頂点から来たかを記録しておけばよいです。
たとえば、以下のように DP テーブルを定義します。
from[S][v] := DP[S][v] が表すパスで、v の直前に訪れた頂点として考えられるもののうちの 1 つ (ただし、S は集合の bitmask を整数で表現したものとします)
このとき、DP[S][v] からの遷移を以下のように変更することで、from[S][v] を求めることができます。
// 更新がおこなわれたときだけ、from[S][v] を更新する
if DP[S + 2^u][u] > DP[S][v]:
DP[S + 2^u][u] = DP[S][v]
from[S + 2^u][u] = v
これをすべての S, v, u について実行した後、from[2^n - 1][0] から 0 に向かってたどっていくことで、ハミルトン閉路を構築することができます。
- 入力される値
-
n
a_{1,1} a_{1,2} ... a_{1,n}
a_{2,1} a_{2,2} ... a_{2,n}
...
a_{n,1} a_{n,2} ... a_{n,n}
・ 1 行目に、グラフの頂点数を表す整数 n が与えられます。
・ 続く n 行では、グラフの隣接行列の各要素を表す整数 a_{i,j} が半角スペース区切りで与えられます。(1 ≦ i, j ≦ n) a_{i,j} は、頂点 i から頂点 j への辺のコストを表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行目に、最小のコストを表す整数を出力してください。
2 行目に、最小のコストを持つハミルトン閉路を表す頂点の番号を左から順番に半角スペース区切りで出力してください。
最初の頂点の番号と最後の頂点の番号が同じになるように n 個の頂点を出力してください。
正しい答えであれば、どれを出力してもかまいません。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 18
・ 0 ≦ a_{i,j} ≦ 100 (1 ≦ i, j ≦ n)
・ a_{i,i} = 0 (1 ≦ i ≦ n)
- 入力例1
-
3
0 2 3
3 0 2
2 3 0
- 出力例1
-
6
1 2 3
- 入力例2
-
4
0 42 57 17
96 0 95 25
12 94 0 57
81 35 5 0
- 出力例2
-
84
2 4 3 1
