개발자 크루

[RecurDyn]

취미로 코딩하는 RecurDyn 개발자 모임

Lv.4

썸네일

더블! 산타 외판원 순회

난이도
4 단계
참가자
0 명
제출
0 명
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 1초 1024MB
Java 1초 1024MB
Python 2초 1024MB
C++ 1초 1024MB
JavaScript 2초 1024MB

두 명의 산타가 n개의 도시에 선물을 주려고 합니다. 두 산타는 서로 방문하는 도시가 겹치지 않게 방문하려 하고, 모든 도시는 다 방문되어야만 합니다. 또한 각 산타가 방문하는 방식은 외판원 순회(TSP)와 같아서, 임의의 시작 도시로부터 이동한 뒤에는 다시 시작 도시로 돌아와야만 합니다. 각 산타는 최소 2개 이상의 도시를 방문해야만 한다 했을 때, 모든 도시를 방문하기 위해 두 산타가 이동해야 하는 이동거리의 합 중 가능한 최솟값을 구하는 프로그램을 작성해보세요.





본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

  • 4 ≤ n ≤ 14
  • 0 ≤ cost[i][j] ≤ 1,000,000

입력형식

첫 번째 줄에는 도시의 수를 나타내는 n이 주어집니다.

두 번째 줄 부터는 n개의 줄에 걸쳐서 비용 행렬이 주어집니다. cost[i][j] 는 도시 i에서 j로 가기 위한 비용을 나타내며, 0인 경우 이동이 불가능함을 뜻합니다.

출력형식

두 산타가 모든 도시를 방문하기 위해 필요한 이동거리의 합 중 최솟값을 출력합니다. 불가능한 경우는 없다고 가정해도 좋습니다.

입력예제1

4
0 10 10 10
10 0 7 10
10 8 0 10
10 10 10 0
출력예제1

35
입력예제2

5
0 10 10 6 10
10 0 7 10 5
10 6 0 10 5
10 10 6 0 10
10 4 10 10 0
출력예제2

31