# KGP14G - Editorial

Editorialist: Lalit Kundu

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.