# Finding shortest path involving additional restrictions

Question: If you were on an island(Vertex) which are connected to multiple other islands, and to get from island A to B it takes time T and does damage D to your boat. What is the fastest route from A to B such that the total damage is strictly less than a given value H.

I tried using Dijkstra's algorithm to build a sub-tree however the shortest route may not be acceptable since the total damage could be greater than H. Any suggestions? Please keep the answer simple since I am a high school student.

We can create a new graph consisting of $N\cdot (H + 1)$ nodes and apply the Dijkstra algorithm on that graph. We will denote the new nodes as $(u, h):$ which means that the boat is at island $u$ and has been damaged by $h$ units, where $h$ is between $0$ and $H$. For each edge $(u, v, d, t)$ that goes from island $u$ to island $v$ while taking $d$ damage and $t$ time, we will create multiple edges in the new graph $((u, h), (v, h+d), t)$ (for $0 \leq h \leq H-d$). Your starting node will be $(A, 0)$ and to find the shortest path to $B$ you need to apply the Dijkstra algorithm and take the minimum time to $(B, h)$ for some $h$ between $0$ and $H$.