巡回セールスマン問題 (bitmask DP) Erlang(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
巡回セールスマン問題 (TSP) とは、辺にコストが付いたグラフが与えられたときに、コストの総和が最小になるようなハミルトン閉路を求める問題です。
有向グラフの各辺のコストを表す隣接行列が与えられるので、巡回セールスマン問題の解、すなわちハミルトン閉路のコストの総和の最小値を求めてください。
今回は n が最大で 18 と、全探索では間に合わないサイズになっています。そのため、bitmask DP を用いて解く必要があります。
ここで、以下のように DP テーブルを定義します。
DP[S][v] := 頂点集合 S に含まれる頂点をすべて訪問した状態で頂点 v にいるようなパスのコストの総和の最小値 (ただし、S は集合の bitmask を整数で表現したものとします)
このとき、DP[S][v] から以下のように遷移することで、DP テーブルを更新することができます。
DP[S + 2^u][u] = min(DP[S + 2^u][u], DP[S][v] + (v, u) のコスト) (u は S に含まれていない頂点で、辺 (v, u) が存在し、v ≠ u)
これをすべての S, v, u について実行した後、DP[2^n - 1][0] を出力すればよいです。
なお、DP[0][0] を 0 で、それ以外を十分大きな値で初期化しておく必要があります。
また、bitmask の集合表現では番号が 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 ≦ 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
- 入力例2
-
4
0 42 57 17
96 0 95 25
12 94 0 57
81 35 5 0
- 出力例2
-
84
