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