관광 투어
시간 제한8초메모리 제한512 MB
완전 그래프의 모든 간선을 최소 비용으로 방향을 정해, N개 지역을 모두 한 번씩 지나는 해밀턴 경로가 존재하도록 만든다.
문제
KM 도시에는 N개의 관광 구역이 있다. 현재 모든 구역 쌍은 양방향 도로로 연결되어 있다.
그런데 어떤 이유에서인지 KM 도시의 시장인 KM 씨는 이 도로들을 전부 일방통행으로 바꾸기로 했다. 구역 i와 구역 j 사이의 도로를 구역 i에서 구역 j로 가는 일방통행 도로로 개조하는 데는 Ci,j달러가 든다. 물론 KM 씨는 경제적이므로 개조 비용의 총합을 최소화하려 한다.
한편 KM 도시에서 관광은 가장 중요한 산업이므로, 모든 관광 구역을 정확히 한 번씩 방문하는 투어가 존재해야 한다. 이 경로의 첫 구역과 마지막 구역은 같지 않아도 된다. 이 상황에서 개조에 필요한 최소 총비용을 계산할 수 있는가?
입력
첫째 줄에는 관광 구역의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 정수 행렬 C가 주어지며, i번째 줄의 j번째 원소는 Ci,j를 나타낸다. (0 ≤ Ci,j ≤ 1, 000, 000) 모든 i에 대해 Ci,i는 항상 0이다.
출력
최소 비용을 한 줄에 출력한다.