O: Road Trip

https://open.kattis.com/problems/roadtrip

Keep track of your total cost, current gas, current station, and furthest station you can get to with your current gas at all times.

Then repeatedly:

(1) Find the cheapest station between your current station and the furthest station you can get to

(2) Move there (i.e. update current station and subtract from current gas)

(3) Update the furthest station pointer (either find the next station that sells gas for cheaper than this station within range, or the furthest station you can get to if you fully fill up the tank)

(4) If there isn’t a cheaper station in range, fully fill up gas (update total cost and current gas). Otherwise, fill up exactly enough to make it to the cheaper station.

(5) Move up one station (so you don’t get stuck infinitely at a cheap station)

Fail if you ever don't have enough gas to complete step (5) since that means you’re stuck at a station.

For implementation, every time you do step (3) add all the new stations up to the new furthest stations to a priority queue. Then to find the cheapest station keep popping off the top of the priority queue until you find a station between your current and furthest station.