한 무대에서 오늘 하루 동안 \(N\) 개의 공연을 모두 한 번씩, 어떤 순서로든 진행해야 합니다. 맨 처음에 진행하는 공연 \(i\) 는 무대를 처음부터 세팅해야 하므로 준비 비용 \(S_i\) 가 듭니다. 그 뒤로 공연 \(u\) 를 마치고 바로 공연 \(v\) 로 무대를 전환하면 전환 비용 \(T_{uv}\) 가 듭니다.

모든 공연을 한 번씩 진행하는 순서 중에서 (첫 준비 비용 + 모든 전환 비용)의 합을 최소로 만드는 값을 구하세요. 마지막 공연 후 다시 돌아올 필요는 없습니다(경로, 사이클 아님).

\(N \le 15\) 이므로 "이미 진행한 공연 집합"과 "마지막 공연"을 상태로 하는 비트마스크 DP로 해결합니다.

• \(1 \le N \le 15\)
• \(0 \le S_i \le 500\)
• \(0 \le T_{uv} \le 1000\), \(T_{ii}=0\)

첫 줄에 공연 수 \(N\) 이 주어집니다.

둘째 줄에 \(N\) 개의 준비 비용 \(S_0, \dots, S_{N-1}\) 이 주어집니다.

이어서 \(N\) 개의 줄에 전환 비용 행렬 \(T\) 가 주어집니다 (\(T_{ii}=0\)).

가능한 최소 총 비용을 한 줄에 출력합니다.

riseoj 작성

출처 Original