PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM-HARD
PRE-REQUISITES:
Dynamic Programming, Shortest Path Algorithms
PROBLEM:
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.
EXPLANATION:
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[1][6]=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.
ALTERNATIVE SOLUTION:
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.