문제
당신은 N개의 도시를 최소비용으로 한 번씩 방문하려고 한다. 하지만 가장 효율적인 경로를 구하는 것은 매우 어려운 일이다. 따라서 당신은 다음과 같은 제약조건을 덧붙이기로 했다.
조건) 임의의 K( 1<= K <=N)번 도시를 방문하기 전에 1~K-1번 도시를 모두 방문하거나 K번 도시를 방문한 후에 1~K-1번 도시를 모두 방문해야 한다.
각 도시 간 통행비용이 주어질 때 모든 도시를 방문하기 위한 최소비용을 구하여라. 출발 도시와 도착 도시는 마음대로 정할 수 있다.
입력
첫 번째 줄에는 도시의 수 N이 주어진다. (1 ≤ N ≤ 1,500)
두 번째 줄부터 N개의 줄에는 아래 형식에 맞게 수들이 주어진다.
- A+1번째 줄의 B번째 수는 도시 A에서 도시 B까지 갈 때 드는 비용이다.
도시 A에서 도시 B로 갈 때 드는 비용과 도시 B에서 도시 A로 갈 때 드는 비용은 같고, 도시 A에서 도시 A로 가는 비용은 0이다. 모든 비용은 1,000 이하이다.
전체 데이터의 1/3은 N ≤ 10이며, 전체 데이터의 1/2는 N ≤ 20이다.
출력
모든 도시를 방문할 때 드는 최소비용을 출력한다.
예제1
입력
3
052
504
240
출력
7
예제2
입력
4
01578
150169
716012
89120
출력
31
힌트
출처
COCI 2013/2014 - Contest 2