COCI 2013/2014 - Contest 2- 여행 (PUTNIK) > 문제은행 : 정보올림피아드&알고리즘




2665 : 여행 (PUTNIK)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
10 회   
시도횟수
16 회   

문제

당신은 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이다.

출력형식

모든 도시를 방문할 때 드는 최소비용을 출력한다.

입력 예

3
0 5 2
5 0 4
2 4 0

출력 예

7

입력 예

4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0

출력 예

31

Hint!

2-1-3 또는 3-1-2의 경로로 도시를 방문한다면 7의 비용이 든다. 1-3-2의 경로로 도시를 방문한다면 6의 비용이 들지만 조건을 만족하지 않는다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP