시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 6 4 (67%) 4
문제
당신은 외판원 문제(Travelling Salesman Problem; TSP)에 대해 들어 볼 기회가 있었을지 모른다. 당신이 알고 있다면, 이 문제는 효율적인 해법이 없기 때문에 NP-hard 문제라는 것도 알고 있을 것이다. 이 문제는 외판원 문제의 흔치 않은 형태이다! 이 흔치 않음에 의해서 이 문제는 효율적으로 해결하는 것이 가능하다. 외판원은 $N$개의 도시를 각각 한번씩 방문해야 하는 임무를 받게 되었다. 도시는 $1, 2, …, N$의 번호로 나타나며, 우리는 각 도시간을 직행하는 비행기편의 시간이 얼마나 걸리는지를 알고 있다. 외판원은 효율적인 것을 좋아하는 사람이기 때문에, 도시를 방문하는 순서를 조정하여 모든 도시를 방문하는 데 드는 시간을 최소화하고자 한다. 유감스럽게도, 일은 그다지 쉽지 않았다. 외판원은 도시를 방문하는 순서에 대해 이상한 집착을 가지고 있었기 때문이다. **각각의** 도시 $K$에 대해 $K$보다 번호가 적게 붙은 모든 도시를 $K$를 방문하기 이전에 방문하거나, $K$를 방문한 이후에 방문해야 한다는 집착이다. 다른 말로 하면, $K$를 방문하기 이전에 $K$보다 번호가 적은 도시를 방문했다면, $K$보다 번호가 적은 도시는 $K$를 방문한 다음에는 방문할 수 없다는 뜻이다. 이 외판원의 야심찬 계획을 도와서 모든 도시를 방문하기 위해 드는 전체 비행 시간의 최솟값을 구해주자. 어떤 도시에서 출발해도 상관없고, 어떤 도시에서 끝나도 상관없다. 단지 모든 도시를 정확히 한 번 방문해야 하고, 외판원의 집착을 만족하면 된다.
입력
첫 번째 줄에는 도시의 수를 나타내는 양의 정수 $N (2 \leq N \leq 1,500)$이 주어진다. 다음 $N$개의 줄의 각 줄에는 $N$개의 양의 정수가 주어진다. 각 정수는 $0$ 이상 $1,000$이하이다. $A$번째 줄에 있는 $B$번째 정수는 $A$번 도시와 $B$번 도시를 오가는 데 드는 시간이다. 이는 $B$번째 줄의 $A$번째 정수의 값과 같다. 만약 $A = B$이면 $0$이고, 아닌 경우에는 양의 정수로 주어진다. 전체 테스트 중의 $\frac{1}{3}$은 $N$이 $10$보다 작거나 같다. 전체 테스트 중의 $\frac{1}{2}$은 $N$이 $20$보다 작거나 같다.
출력
첫 번째 줄에 모든 도시를 방문하기 위해 드는 전체 비행 시간의 최솟값을 출력한다.
힌트
### 예제 #### 입력 1 ``` 3 0 5 2 5 0 4 2 4 0 ``` #### 출력 1 ``` 7 ``` 최적의 방문 순서는 $2, 1, 3$또는 $3, 1, 2$이다. $1, 3, 2$가 좀 더 빠르지만, 이는 외판원의 집착을 충족하지 못한다.
#### 입력 2 ``` 4 0 15 7 8 15 0 16 9 7 16 0 12 8 9 12 0 ``` #### 출력 2 ``` 31 ``` 최적의 방문 순서는 $3, 1, 2, 4$또는 $4, 2, 1, 3$이다.