5245 : A46 - 휴리스틱 1
•시간제한: 5.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}$ 입니다.
도시 1에서 출발하여 모든 도시를 한 번씩 방문한 뒤 다시 도시 1로 돌아오는 경로 중, 총 거리가 가능한 짧은 경로를 출력하세요.
[제약 조건]
• $1 \le N \le 500$
• $1 \le a_i,b_i,c_i \le 10^9$
• $x+y$ 가 최대가 될 때, $x$ 와 $y$ 는 모두 양의 실수입니다.
도시 $i$ 는 좌표 $ (X_i, Y_i) $ 에 있으며, 도시 $i$ 에서 도시 $j$ 까지의 거리는 $\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2}$ 입니다.
도시 1에서 출발하여 모든 도시를 한 번씩 방문한 뒤 다시 도시 1로 돌아오는 경로 중, 총 거리가 가능한 짧은 경로를 출력하세요.
[제약 조건]
• $1 \le N \le 500$
• $1 \le a_i,b_i,c_i \le 10^9$
• $x+y$ 가 최대가 될 때, $x$ 와 $y$ 는 모두 양의 실수입니다.
입력 설명
첫째 줄에 정수 $N$ 이 주어집니다.
둘째 줄부터 $N$ 개의 줄에 걸쳐 각 도시의 좌표 $X_i, Y_i$ 가 주어집니다.
둘째 줄부터 $N$ 개의 줄에 걸쳐 각 도시의 좌표 $X_i, Y_i$ 가 주어집니다.
출력 설명
방문하는 도시의 번호를 순서대로 $N+1$ 개 출력하세요. (처음과 마지막은 1이어야 합니다)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
1 1
4 1
2 5
3 4
3 2
4 2
5 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
5
6
2
4
3
7
1