minimum number of days to reach destination | graph

user_13952905 0
Viewed 549

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).

graph algorithm
1 Answers

This can be done with Dijkstra:

  • lets say our dijkstra state is {daysPassed, timeTravelled, vertexId}
  • initial state is {0,0,startCity} we add it to priority queue (sorted as tuples, min first)
  • For each state in queue:
  • try going to all neighboring cities (if timeTravelled + edgeWeigth <= maxTravelTimePerDay), state changes to {daysPassed, timeTravelled + edgeWeight, neighbourId}
  • try to sleep in current city (if it has a hotel), state changes to {daysPassed + 1, 0, vertexId}
  • Of course its not profitable to sleep in same hotel 2 times so we can additionally keep a boolean array indicating whether we slept in some hotel and only try to sleep in hotel once (on first time visiting vertex)
  • if any time during algorithm we reach goal city daysPassed from state is the answer
user_40591450
Related