문제
당신은 N개의 도시를 최소비용으로 한 번씩 방문하려고 한다. 하지만 가장 효율적인 경로를 구하는 것은 매우 어려운 일이다. 따라서 당신은 다음과 같은 제약조건을 덧붙이기로 했다.
조건) 임의의 K( 1<= K <=N)번 도시를 방문하기 전에 1~K-1번 도시를 모두 방문하거나 K번 도시를 방문한 후에 1~K-1번 도시를 모두 방문해야 한다.
각 도시 간 통행비용이 주어질 때 모든 도시를 방문하기 위한 최소비용을 구하여라. 출발 도시와 도착 도시는 마음대로 정할 수 있다.
입력
첫 번째 줄에는 도시의 수 N이 주어진다. (1 ≤ N ≤ 1,500)
두 번째 줄부터 N개의 줄에는 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
0 5 2
5 0 4
2 4 0
7
2-1-3 또는 3-1-2의 경로로 도시를 방문한다면 7의 비용이 든다. 1-3-2의 경로로 도시를 방문한다면 6의 비용이 들지만 조건을 만족하지 않는다.
예제 #2
4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0
31
출처
COCI 2013/2014 - Contest 2
로그인해야 코드를 작성할 수 있어요.