우주 탐사선

면접 대비

시간 제한1초메모리 제한512 MB

요약
행성 사이 이동 시간과 시작 행성이 주어질 때, 모든 행성을 방문하는 최단 경로의 시간을 구한다. 시작 행성으로 돌아올 필요는 없다.
난이도

보통10점 중 6점

유형
동적 계획법, 비트 연산, 그래프, 완전 탐색
정답자
아직 제출이 없습니다

문제

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는 데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐사할 행성의 개수, ana호가 발사되는 행성의 위치, ana호가 행성 간을 이동하는 데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하며, 0은 행렬에서 0번째 인덱스에 해당하는 행성을 뜻한다. 2차원 행렬에서 i번째 행 j번째 열의 원소는 i번째 행성에서 j번째 행성에 도달하는 데 걸리는 시간이다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는 데 걸리는 최소 시간을 계산하여라.

탐사를 마친 뒤 다시 시작 행성으로 돌아올 필요는 없으며, 이미 방문한 행성도 중복해서 갈 수 있다.

입력

첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N줄에 걸쳐 각 행성 간 이동 시간 Tij가 N개씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij ≤ 1000)

출력

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

예제2

  1. 예제 1

    입력
    3 0
0 30 1
1 0 29
28 1 0
    예상 출력
    2

  2. 예제 2

    입력
    4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0
    예상 출력
    74