#1976 승현이의 여행

15  1 s   128 MB  

Description

아주대학교 11학번 박승현을 도와 아주대학교에서 출발하여 모든 여행지를 이동할때 최단경로를 찾아주는 프로그램을 작성하시오

Input

입력의 첫줄에는 여행지의 갯수를 나타내는 (1<=N<=10)이 주어진다.

입력의 둘째줄 부터 N+1줄 까지는 여행지의 이름과 위치를 나타내는 정수좌표 (x,y)가 주어진다.

Output

출력의 첫째줄에는 아주대학교[위치 : (0,0)]에서 출발하여 모든 여행지를 방문할때 최단경로가 되는 경로를 출력하시오

둘째줄에는 최단경로가 되는 경로의 이동거리를 소숫점 셋째 자리에서 반올림하여 출력하시오.

 

Sample Input

Sample Output

2
AMERICA 100 100
KOREA 50 50
AJOU -> KOREA -> AMERICA
141.42

HINT

(정답은, double로 표현할수 있는 범위입니다.)