巡回セールスマン問題 (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

巡回セールスマン問題 (TSP) とは、辺にコストが付いたグラフが与えられたときに、コストの総和が最小になるようなハミルトン閉路を求める問題です。

有向グラフの各辺のコストを表す隣接行列が与えられるので、巡回セールスマン問題の解、すなわちハミルトン閉路のコストの総和の最小値を求めてください。

入力される値

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 への辺のコストを表します。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 8
・ 0 ≦ a_{i,j} ≦ 100 (1 ≦ i, j ≦ n)
・ a_{i,i} = 0 (1 ≦ i ≦ n)