발전소 설치
시간 제한2초메모리 제한128 MB
이미 있는 케이블은 비용이 0이고 새 케이블은 길이가 M 이하일 때만 놓을 수 있는 상황에서, 1번과 N번 발전소를 잇는 데 필요한 최소 신규 케이블 길이를 구합니다.
문제
강한 낙뢰로 많은 전선이 끊어져 전력 공급이 중단되었다. 우선 1번 발전소와 N번 발전소가 다시 서로 이어지도록 해야 한다.
발전소는 1번부터 N번까지 번호가 붙어 있으며 2차원 격자 좌표 위에 놓여 있다. 일부 전선은 아직 남아 있어 몇몇 발전소를 서로 잇고 있다. 현재 남아 있는 전선과 발전소의 위치가 주어질 때, 추가로 설치하는 전선 길이의 합을 최소화하여 1번 발전소와 N번 발전소를 연결해야 한다. 연결 경로는 다른 발전소들을 거쳐도 된다. 단, 안정성 때문에 두 발전소를 직접 잇는 전선의 길이는 M을 초과할 수 없다. 아래 그림은 한 가지 연결 예시이다.
연결 전 연결 후
3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . .
/
2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . .
/
1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . .
| |
0 1 . . . . . . . . . 0 1 . . . . . . . . .
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
입력
첫째 줄에 발전소의 수 N(1 <= N <= 1,000)과 현재 남아 있는 전선의 수 W(1 <= W <= 10,000)가 주어진다. 둘째 줄에 제한 길이 M(0.0 < M < 200,000.0)이 주어진다.
다음 N개 줄에는 1번 발전소부터 N번 발전소까지 각 발전소의 X좌표와 Y좌표 xi, yi(-100,000 <= xi, yi <= 100,000)가 순서대로 주어진다. 이어지는 W개 줄에는 현재 남아 있는 전선이 잇는 두 발전소의 번호가 정수로 주어진다.
출력
1번 발전소와 N번 발전소를 연결하기 위해 추가로 필요한 전선 길이의 최솟값에 1000을 곱한 뒤, 소수점 아래를 버린 정수를 출력한다.