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