leeingyun96   2년 전

트리가 아닌 별

 

문제

루크는 자신의 집 컴퓨터 네트워크를 업그레이드하려고 합니다.

인터넷이 정상 작동하려면 모든 컴퓨터에 대해, 컴퓨터-컴퓨터로 연결되거나 컴퓨터-허브로 연결되어야 합니다. 루크는 프림 알고리즘이나 크루스칼 알고리즘에 대해 모르기 때문에 컴퓨터들을 연결하는 방법을 모릅니다. 그래서 모든 컴퓨터를 하나의 허브로 연결시키려고 합니다.

연결을 시키기 위해서는 케이블이 필요하고 필요한 케이블의 총 길이를 최소화하려고 합니다.

 

입력

입력의 첫 줄은 양의 정수 N <= 100, 컴퓨터의 개수를 포함합니다. 그 다음 N줄에 대해, 각 줄마다 하나의 컴퓨터의 (x, y) 좌표가 mm 단위로 주어집니다.모든 좌표는 0과 10,000 사이의 정수입니다.

 

출력

출력은 한 숫자를 포함합니다. 가장 가까운 mm로 반올림된 케이블의 총 길이입니다.

댓글을 작성하려면 로그인해야 합니다.