개발자 크루
남양연구소입니다.
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