7203 : 비트마스크 방문
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 노드가 있고, 각 노드 간의 이동 가중치가 인접 행렬로 주어집니다. 0번 노드에서 출발하여 모든 노드를 한 번씩 방문하고 다시 0번 노드로 돌아오는 최소 비용을 구하십시오. (TSP)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 노드의 수 N이 주어집니다. (1 ≤ N ≤ 15)
둘째 줄부터 N개의 줄에 걸쳐 인접 가중치 행렬(N×N)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 인접 가중치 행렬(N×N)이 주어집니다.
출력 설명
최소 방문 비용을 출력합니다. 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
35도움
0 → 1 → 3 → 2 → 0 경로의 비용이 10 + 10 + 9 + 6 = 35 로 최소입니다.