Delivering Rice Cakes
InterviewTime limit1sMemory limit512 MB
Given a weighted graph, a start house Y, and a daily walking limit X, find how many days it takes to visit every other house if each day's trip must return to Y and stay within X.
- Level
Medium6 of 10
- Topics
- Graph, Shortest path, Greedy, Sorting
- Solved
- No attempts yet
Problem
Seonghyeon, a soldier, moved into a new house after being discharged. Wanting to get along with the neighbors, he decided to deliver rice cakes to the neighboring houses. He can carry only one rice cake at a time. There are M bidirectional roads between the houses in total.
Seonghyeon finds this tiresome, so he does not walk more than X per day and visits the closest houses first. He also insists on sleeping at his own house, so he resolves to visit any house he cannot make a round trip to on the next day. What is the minimum number of days needed to deliver rice cakes to all N-1 neighboring houses?
The houses are numbered 0 through N-1 in order.
Input
The first line gives N, M, X, Y separated by spaces. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)
From the second line to the M+1-th line, A, B, and the length C of the road between house A and house B are given. (0 ≤ A,B < N, 1 ≤ C ≤ 10,000) A and B are distinct, and C is an integer.
The road connecting house A and house B is unique.
Output
Given that Seonghyeon's house is Y, print the minimum number of days needed to deliver rice cakes to all the neighboring houses. If he cannot visit them all, print -1.