Informatica Online Judge

  택배 배달 (TSP) [0765 / 02FD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 51   Total Tried : 85


The Champion of this Problem (C++) : gs15120 - 26ms / 1475byte
My Best Submission (C++) : N/A

[]

Background

택배회사 GSHS는 오늘도 택배를 배달한다. 오늘 배달할 N개의 택배와 배송지를 받았다.

택배직원 경곽이는 머리가 매우 뛰어나다. 따라서 오늘 배달할 N개의 택배를 모두 배달하고 다시 회사로 돌아오는 거리의 길이를 최소화 하고자 한다.

택배회사의 위치는 좌표평면상에 (0,0)에 위치한다. N개의 배송지의 주소가 주어질 때,모든 장소에 배달하고 회사로 돌아오는 최소 거리를 구하는 프로그램을 작성하시오.
(단, 거리는 Manhattan distance(Taxi distance)로 계산한다.)

Input

첫 번째 줄에 배송지의 수 N이 입력된다. (단 N은 10이하의 자연수이다.)
두 번째 줄부터 N줄에 걸쳐서 각 배송지의 좌표가 주어진다. (좌표는 절댓값 10,000이하의 정수, 단 같은 배송지는 존재하지 않는다.)

Output

모든 택배를 배달하고 회사로 돌아오는 최소 거리를 구한다.

IO Example

입력
3
1 0
1 1
0 1

출력
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]