E - 工場の解体作業 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は解体工事の現場監督です。ある工業団地に N 棟の建物があり、それぞれ 1 から N の番号が付けられています。高橋君はこれらすべての建物を1棟ずつ、ちょうど1回ずつ解体していきます。

各建物 i（1 \leq i \leq N）には初期解体コスト C_i が設定されています。建物 i を解体するときには、その時点での建物 i の解体コストを費用の合計に加算します。解体コストは負の値になることもあり、その場合は費用の合計が減少します。

建物同士は配管や配線で影響を及ぼし合うことがあります。具体的には、建物 i を解体した直後、まだ解体されていない各建物 j の解体コストに W_{i,j} が加算されます。ここで W_{i,j} は正の場合も負の場合も 0 の場合もあります。建物 i を先に解体することで隣接する建物 j の作業がやりやすくなり解体コストが下がることもあれば、逆に支えを失って解体コストが上がることもあります。なお、既に解体済みの建物には影響しません。

高橋君は解体する順番を自由に決めることができます。すべての建物を解体するために必要な費用の合計を最小化してください。費用の合計の最小値を求めてください。なお、費用の合計は負になることもあります。

制約

  • 1 \leq N \leq 19
  • -10^6 \leq C_i \leq 10^6 \quad (1 \leq i \leq N)
  • -10^6 \leq W_{i,j} \leq 10^6 \quad (1 \leq i, j \leq N, \; i \neq j)
  • W_{i,i} = 0 \quad (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N
C_1 C_2 \ldots C_N
W_{1,1} W_{1,2} \ldots W_{1,N}
W_{2,1} W_{2,2} \ldots W_{2,N}
\vdots
W_{N,1} W_{N,2} \ldots W_{N,N}
  • 1 行目には、建物の棟数を表す整数 N が与えられる。
  • 2 行目には、各建物の初期解体コストを表す整数 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。
  • 続く N 行にわたって、解体による他の建物へのコスト変動を表す整数 W_{i,j} が与えられる。このうち i 行目（1 \leq i \leq N、入力全体では i+2 行目）には W_{i,1}, W_{i,2}, \ldots, W_{i,N} がスペース区切りで与えられる。W_{i,j} は建物 i を解体した際に、まだ解体されていない建物 j の解体コストに加算される値である。W_{i,i} は常に 0 である。

出力

すべての建物を解体するために必要な費用の合計の最小値を、1行で出力せよ。

入力例 1

3
10 20 30
0 5 -10
2 0 3
-4 1 0

出力例 1

55

入力例 2

2
-5 7
0 -3
10 0

出力例 2

-1

入力例 3

7
15 -8 23 0 42 -17 6
0 4 -2 7 0 -5 3
-6 0 8 -1 2 0 -4
5 -3 0 6 -7 1 0
0 9 -5 0 4 -2 8
-1 0 3 -6 0 7 -8
2 -4 0 5 -9 0 6
-7 1 4 0 3 -2 0

出力例 3

28

入力例 4

12
100 -200 50 0 300 -150 75 125 -60 220 -310 40
0 12 -7 0 35 -20 5 -11 18 0 -9 14
-30 0 22 -5 0 17 -13 8 -1 26 0 -16
4 -18 0 31 -6 0 12 -24 9 -3 15 0
0 7 -21 0 10 -14 0 19 -8 6 -25 11
-12 0 5 -9 0 28 -17 0 13 -4 20 -6
23 -10 0 16 -2 0 7 -15 0 21 -11 3
-5 14 -8 0 24 -19 0 6 -12 0 27 -1
9 -3 18 -22 0 11 -7 0 4 -16 2 25
-14 6 0 20 -10 0 15 -5 0 8 -18 12
0 -24 13 -1 7 -9 0 17 -6 0 10 -20
19 0 -4 12 -23 5 -2 0 16 -8 0 30
-7 21 0 -15 3 -12 9 -18 0 14 -5 0

出力例 4

-86

入力例 5

1
-1000000
0

出力例 5

-1000000

Score : 466 pts

Problem Statement

Takahashi is a demolition site supervisor. There are N buildings in an industrial park, numbered 1 to N. Takahashi will demolish all of these buildings one by one, each exactly once.

Each building i (1 \leq i \leq N) has an initial demolition cost C_i. When building i is demolished, its demolition cost at that moment is added to the total cost. The demolition cost can be negative, in which case the total cost decreases.

Buildings can affect each other through piping or wiring. Specifically, immediately after building i is demolished, W_{i,j} is added to the demolition cost of each building j that has not yet been demolished. Here, W_{i,j} can be positive, negative, or 0. Demolishing building i first may make the work on an adjacent building j easier, reducing its demolition cost, or it may lose support, increasing the cost. Note that this does not affect buildings that have already been demolished.

Takahashi can freely choose the order of demolition. Minimize the total cost required to demolish all buildings. Find the minimum possible total cost. Note that the total cost can be negative.

Constraints

  • 1 \leq N \leq 19
  • -10^6 \leq C_i \leq 10^6 \quad (1 \leq i \leq N)
  • -10^6 \leq W_{i,j} \leq 10^6 \quad (1 \leq i, j \leq N, \; i \neq j)
  • W_{i,i} = 0 \quad (1 \leq i \leq N)
  • All input values are integers.

Input

N
C_1 C_2 \ldots C_N
W_{1,1} W_{1,2} \ldots W_{1,N}
W_{2,1} W_{2,2} \ldots W_{2,N}
\vdots
W_{N,1} W_{N,2} \ldots W_{N,N}
  • The first line contains an integer N, representing the number of buildings.
  • The second line contains space-separated integers C_1, C_2, \ldots, C_N, representing the initial demolition cost of each building.
  • The following N lines contain integers W_{i,j} representing the cost changes to other buildings due to demolition. The i-th of these lines (1 \leq i \leq N, which is the (i+2)-th line of the entire input) contains space-separated integers W_{i,1}, W_{i,2}, \ldots, W_{i,N}. W_{i,j} is the value added to the demolition cost of building j (if it has not yet been demolished) when building i is demolished. W_{i,i} is always 0.

Output

Print the minimum total cost required to demolish all buildings in a single line.

Sample Input 1

3
10 20 30
0 5 -10
2 0 3
-4 1 0

Sample Output 1

55

Sample Input 2

2
-5 7
0 -3
10 0

Sample Output 2

-1

Sample Input 3

7
15 -8 23 0 42 -17 6
0 4 -2 7 0 -5 3
-6 0 8 -1 2 0 -4
5 -3 0 6 -7 1 0
0 9 -5 0 4 -2 8
-1 0 3 -6 0 7 -8
2 -4 0 5 -9 0 6
-7 1 4 0 3 -2 0

Sample Output 3

28

Sample Input 4

12
100 -200 50 0 300 -150 75 125 -60 220 -310 40
0 12 -7 0 35 -20 5 -11 18 0 -9 14
-30 0 22 -5 0 17 -13 8 -1 26 0 -16
4 -18 0 31 -6 0 12 -24 9 -3 15 0
0 7 -21 0 10 -14 0 19 -8 6 -25 11
-12 0 5 -9 0 28 -17 0 13 -4 20 -6
23 -10 0 16 -2 0 7 -15 0 21 -11 3
-5 14 -8 0 24 -19 0 6 -12 0 27 -1
9 -3 18 -22 0 11 -7 0 4 -16 2 25
-14 6 0 20 -10 0 15 -5 0 8 -18 12
0 -24 13 -1 7 -9 0 17 -6 0 10 -20
19 0 -4 12 -23 5 -2 0 16 -8 0 30
-7 21 0 -15 3 -12 9 -18 0 14 -5 0

Sample Output 4

-86

Sample Input 5

1
-1000000
0

Sample Output 5

-1000000