실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
피자 배달부 한민오는 이제 N개의 구역을 담당하는 베테랑 피자 배달부입니다. i번째 구역은 지도의 (x_i, y_i)에 위치해 있습니다. 모든 구역은 지도에 나타낼 수 있는 고유한 좌푯값이 있으며 , x_i와 y_i 모두 정수입니다.
한민오는 개발자에게 N개 구역의 피자 배달 최적 경로를 계산해달라는 요청을 합니다. 한민오는 1번 구역에서 시작해서, 차례로 구역을 방문할 계획입니다. (1번 구역, 그다음 2번 구역, 그다음 3번 구역 등). 마지막으로 N번 구역을 방문하고 다시 1번 구역으로 돌아옵니다. 오토바이로 피자 배달하는 한민오는 북쪽, 남쪽, 동쪽, 서쪽 방향에 있는 구역으로 가는 데 1분의 이동 시간이 소요됩니다. 또한, 한민오는 각 구역을 한 번씩만 배달합니다. (물론 1번 구역은 두 번 배달합니다).
당신은 개발자로서 한민오가 피자 배달을 완료하는 데 걸리는 최소 시간을 결정하는 데 도와주세요.
N 의 범위 : (1 <= N <= 100)
4 2 2 2 4 2 1 1 3
12
출처: USACO 2012 January Contest, Silver Division Problem 1. Delivery Route