Editorialist: Lalit Kundu
Dynamic Programming, Shortest Path Algorithms
K(<500) stations. Connecting flight in between stations denoted by (u,v,s,f,t) where u is the originating location, v is the destination location, s and f are the start and finish of a time interval within which travel can start at u, and t is the travel time in hours from u to v when starting within the closed interval [s,f], as a route.
You need to go from station 1 to station K in minimum time, with some other constraints:
A flight of duration t deprives you of t energy-credits(energy-credits can’t go negative). So you can’t travel in a flight of duration t if at the starting of flight you have less than t energy-credits. Resting at any station(within flights) for duration of t hours gives you t extra energy-credits. You can’t have more than 6 energy-credits, even if you rest for longer duration than that. You start with 6 energy-credits at t=0 from node 1.
Note that journey can span over multiple days.
So, let us define dp[u][e] as the minimum time required to reach node u with energy e. So, now we can apply shortest path algorithm(Dijkstra’s) over time to get the minimum time required to reach node K.
So, we maintain a structure of (node, time, energy) in our dijkstra.
The following psudo code will make it clear:
dp[i][j]=INF, for all i,j dp=0 priority_queue < node > myq; while not myq.empty(): node top = myq.top() myq.pop() cur_node = top.node cur_energy = top.energy cur_time = top.time //assuming we wait at current node for i hours for i=0 to 24: new_energy = min(cur_energy+i,6) new_time = cur_time+i for j=0 to neighbors[cur_node].size() v=neighbors[cur_node].node time_flight=neighbors[cur_node].time start_time=neighbors[cur_node].stime end_time=neighbors[cur_node].etime //possible to take the flight if time_flight <= new_energy and new_time <= end_time and new_time >= start_time //if dp of new node is improved, update it and push to queue and dp[v][new_energy-time_flight] > dp[cur_node][cur_energy]+new_time+time_flight: dp[v][new_energy-time_flight] = dp[cur_node][cur_energy]+new_time+time_flight myq.push(node(v,new_energy-time_flight,dp[v][new_energy-time_flight])
Once we call this dijkstra function, we’ll have to take minimum of all dp[K][i], for i=0 to 6.
Keep a dp state dp[u][h][e] which stores the minimum time to reach city u at hour h and energy e and then apply dijkstra similarly.