NP-hard

외판원 순회 문제(TSP)는 NP-hard라서 도시 수가 조금만 늘어도 빠른 해법을 기대하기 어렵다. 여기서는 방문 순서에 제한을 하나 더 붙인 변형을 푼다.

도시는 $1$번부터 $N$번까지 있고, 두 도시 사이를 오가는 데 걸리는 시간은 모두 주어진다. 모든 도시를 한 번씩 방문하면서 이동 시간의 합을 가장 작게 만들어야 한다.

제한은 이렇다. $K$번 도시를 방문할 때, $K$보다 번호가 작은 도시는 전부 $K$번보다 먼저 방문하거나 전부 $K$번보다 나중에 방문해야 한다. 즉 $K$보다 번호가 작은 도시 중 하나를 $K$번 앞에 두고 다른 하나를 $K$번 뒤에 두면 안 된다.

어느 도시에서 시작하고 어느 도시에서 끝내도 된다. 방문 순서에서 이웃한 두 도시 사이의 시간만 더하며, 마지막 도시에서 첫 도시로 돌아오는 시간은 세지 않는다.

제한을 지키면서 모든 도시를 방문하는 데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $N$이 주어진다. ($2 \le N \le 1500$)

다음 $N$개 줄에는 각각 $N$개의 정수가 주어진다. $A$번째 줄의 $B$번째 수는 $A$번 도시에서 $B$번 도시로 가는 데 걸리는 시간이고, 이 값은 $B$번째 줄의 $A$번째 수와 같다. $A$와 $B$가 같으면 $0$이고, 다르면 $1$ 이상 $1000$ 이하의 정수이다.

제한을 지키면서 모든 도시를 방문하는 데 드는 시간의 최솟값을 첫째 줄에 출력한다.

$N = 3$일 때 방문 순서 $1, 3, 2$를 보자. $3$번보다 번호가 작은 도시는 $1$번과 $2$번인데, $1$번은 $3$번 앞에 있고 $2$번은 $3$번 뒤에 있으므로 제한을 어긴다. $N = 3$에서 제한을 지키는 순서는 $(1, 2, 3)$, $(3, 2, 1)$, $(2, 1, 3)$, $(3, 1, 2)$ 네 가지뿐이다.