Problems
대한민국에 새로운 철도 시스템을 놓고자 한다.
대한민국은 2차원 평면으로 나타낼 수 있으며, 2차원 평면의 점으로 표현되는 도시가 N개 있다.
i번째 도시의 위치는 (x[i], y[i])이다.
i번째 도시와 j번째 도시를 잇는 철도는 (x[i] - x[j])^2 + (y[i] - y[j])^2의 비용이 든다.
하지만, 비용이 C 미만인 철도는 기술의 한계로 건설할 수 없다.
이 상황에서, 대한민국의 모든 도시가 연결 될 수 있도록 하는 철도 시스템의 최소 비용을 구해보자.
Input
첫째 줄에 N,C가 주어진다(N<=2000.C<=1000000)
두 번째 줄부터 각 도시의 위치 (x[i],y[i])가 주어진다.(x[i],y[i]<=1000)
입력으로 주어지는 모든 수는 음이 아닌 정수이다.
Output
철도 시스템의 최소 비용을 출력하라. 단, 가능한 철도 시스템이 없으면 -1을 출력하라.
Example
3 11
0 2
5 0
4 3
46
Source
USACO 2014 March Contest, Silver
You must sign in to write code.