by Andrew Li

We can see that this is simply a shortest path question with the added constraint that the hull damage must not exceed a certain amount.

We can still use Dijkstra's algorithm, except the distance array needs another dimension. Instead of ~dist[i]~ containing the shortest distance from the source to node ~i~, we will instead define ~dist[i][j]~ to be the minimum distance from the source to node ~i~ while sustaining exactly ~j~ cm of damage.

With this in mind, we need to alter Dijkstra's algorithm. Normally, after popping a node from the priority queue, you would loop through all adjacent nodes, updating the shortest path to each adjacent node. For this question, we must consider all adjacent nodes, but also all possible amounts of damage we have currently sustained on the hull. To update an adjacent node, see the following example. Assume you are at node ~1~, and there exists an edge to node ~2~ with length 3 that deals 4 damage to your hull. Then, ~dist[2][j+4] = dist[1][j]+3~ for all ~(0 \le j < K-4)~.

Then, we can simply loop through all possible amounts of damage less than ~K~, and take the best distance to node ~B~ given ~j~ damage ~(0 \le j < K)~.

Note that I use a boolean array called inq here to store whether a node is already in the priority queue. This saves a lot of time as it prevents numerous copies of the same node from being stored in the queue at once.

Thus, the time complexity is the same as for Dijkstra's, except for the factor of ~K~ from considering all damages at each node. The time complexity is ~\mathcal O(K (M + N \log N))~, which will run in time.

Alternate Solution

This is a multigraph, and according to a wise computer science teacher, it cannot be solved except with 3-D dynamic programming. Okay, I give up! There is no way to solve this! Clearly, this was not designed for the average high school student!