巡回セールスマン問題 (時間制約付き)
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
巡回セールスマン問題 (TSP) とは、辺にコストが付いたグラフが与えられたときに、コストの総和が最小になるようなハミルトン閉路を求める問題です。
最初に、有向グラフの各辺のコストを表す隣接行列が与えられます。
今回は、辺だけでなく、頂点の訪問順に対してもコストが発生します。
具体的には、頂点 i が b_i 番目までに訪問されなかった場合に、コスト c_i が発生します。(ちょうど b_i 番目に訪問された場合はコストは発生しません。)
なお、この訪問順は始点を含めずに数え、始点の頂点の次の頂点から 1 番目とし、最後に始点の頂点に戻るときは n 番目とします。
このとき、「(辺のコストの総和) + (頂点の訪問順のコストの総和)」が最小になるような、ハミルトン閉路の合計コストを出力してください。
- 入力される値
-
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}
b_1 c_1
b_2 c_2
...
b_n c_n
・ 1 行目に、グラフの頂点数を表す整数 n が与えられます。
・ 続く n 行では、グラフの隣接行列の各要素を表す整数 a_{i,j} が半角スペース区切りで与えられます。(1 ≦ i, j ≦ n) a_{i,j} は、頂点 i から頂点 j への辺のコストを表します。
・ さらに続く n 行では、頂点の訪問順のコストを表す整数 b_i と c_i が半角スペース区切りで与えられます。(1 ≦ i ≦ n) これは、頂点 i が b_i 番目までに訪問されなかった場合に、コスト c_i が発生することを表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えの整数を 1 行で出力してください。
訪問順には始点を含めないことに注意してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 16
・ 0 ≦ a_{i,j} ≦ 100 (1 ≦ i, j ≦ n)
・ a_{i,i} = 0 (1 ≦ i ≦ n)
・ 1 ≦ b_i ≦ n (1 ≦ i ≦ n)
・ 0 ≦ c_i ≦ 100 (1 ≦ i ≦ n)
- 入力例1
-
3
0 2 3
3 0 2
2 3 0
1 1
2 2
2 3
- 出力例1
-
7
- 入力例2
-
4
0 42 57 17
96 0 95 25
12 94 0 57
81 35 5 0
2 100
3 50
4 25
1 20
- 出力例2
-
104
