This is a question asked in Media.net interview, I have been thinking along the lines of Dijkstra but trying to be greedy in Dijkstra can end up giving no solutions, so I can't come up with a clear way of solving it

Problem: Given a graph in which each node represents a city. Some cities are connected to each other through bidirectional roads. The length of each road is also given. Some of the cities have hotels. Given a start city and a destination city and a value K which represents the maximum distance that can be travelled by a person in one day, find the minimum number of days in which the person can reach his destination (or tell if it is impossible for the given K). (Note : If the distance travelled in one day is exceeding K, the person can rest in the city which has a hotel in it, if there is no hotel in that city this implies you have to choose another path. Next day, the person can start from that city and the distance travelled get reset to 0).
(The last statement was confusing for me, perhaps it means something along if the intended distance exceeds K you have to reset your distance by resting in a city with hotel)

How would you go about solving this one?