5322 : B23 - 외판원 순회 문제
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 평면 위에 $ N $ 개의 도시가 있으며, 각각 $ 1 $ 부터 $ N $ 까지 번호가 붙어 있습니다. 도시 $ i $ 의 좌표는 $ (X_i, Y_i) $ 이며, 두 도시 사이를 이동하는 데는 직선 거리와 같은 시간이 걸립니다. 즉, 도시 $ i $ 에서 $ j $ 까지 이동하는 데 $\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}$ 분이 걸립니다.
어느 도시에서 출발하여 모든 도시를 한 번씩 방문한 후 출발 지점으로 돌아오기 위해 필요한 최소 시간은 몇 분입니까?
[제약 조건]
• $2 \le N \le 15$
• $0 \le X_i \le 1000$
• $0 \le Y_i \le 1000$
• 입력되는 모든 값은 정수입니다.
어느 도시에서 출발하여 모든 도시를 한 번씩 방문한 후 출발 지점으로 돌아오기 위해 필요한 최소 시간은 몇 분입니까?
[제약 조건]
• $2 \le N \le 15$
• $0 \le X_i \le 1000$
• $0 \le Y_i \le 1000$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫 번째 줄에 도시의 수 $ N $ 이 주어집니다.
두 번째 줄부터 $ N $ 개의 줄에 걸쳐 각 도시의 좌표 $ X_i, Y_i $ 가 주어집니다.
두 번째 줄부터 $ N $ 개의 줄에 걸쳐 각 도시의 좌표 $ X_i, Y_i $ 가 주어집니다.
출력 설명
최소 이동 시간을 출력하십시오. (상대 오차 또는 절대 오차가 $ 0.001 $ 이하이면 정답)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 0
0 1
1 0
1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4.000000000000도움
도시 $ 1 \to 2 \to 4 \to 3 \to 5 \to 6 \to 7 \to 1 $ 경로를 통하면 합계 거리가 약 $ 18.87 $ 이 됩니다.