떡 돌리기
면접 대비시간 제한1초메모리 제한512 MB
가중 그래프에서 시작 집 Y와 하루 이동 한도 X가 주어질 때, 매일 Y로 돌아오면서 X 이내로 이동해 다른 모든 집을 방문하는 최소 일수를 구한다.
문제
군인인 성현이는 전역 후 새 집으로 이사했다. 주변 이웃과 친하게 지내고 싶어 이웃집에 떡을 돌리기로 했다. 떡은 한 번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다.
귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고, 거리가 가까운 집부터 방문한다. 또 잠은 꼭 자기 집에서 자야 하므로 왕복할 수 없는 거리는 다음 날 가기로 다짐했다. N-1개의 이웃집 모두에게 떡을 돌리려면 최소 며칠이 걸릴까.
집의 번호는 0번부터 N-1번까지 차례대로 붙어 있다.
입력
첫째 줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)
둘째 줄부터 M+1번째 줄까지 A와 B, 그리고 A집과 B집 사이 도로의 길이 C가 주어진다. (0 ≤ A,B < N, 1 ≤ C ≤ 10,000) 단, A와 B는 서로 다른 수이고, C는 정수이다.
A집과 B집을 연결하는 도로는 유일하다.
출력
성현이의 집을 Y라고 할 때, 이웃집 모두에 떡을 돌리기 위한 최소 일수를 출력한다. 모두 방문할 수 없으면 -1을 출력한다.