[OUTDATED - references petrol and driving rather than penalty score + timer and running]

Hints

• ||Try to solve the problem for a low capacity first||
• ||The problem requires that we find the cheapest solution - how can we model this as a shortest path problem, where moving in the graph corresponds to a change in state / use of money?||
• ||To make your solution work for high capacity, you need to recognise that we can force optimal solutions to follow a certain rule||
• ||Under what scenarios would we arrive at a location with spare fuel, and buy fuel, but not up to the capacity?||

Solution

View Solution

For any particular graph, the following can be made true of an optimal solution: > For two consecutive fuelings, either we run out of petrol at the second stop, or we are at maximum capacity for the first stop. Why is this true? Suppose it wasn't, and we neither ran out of petrol arriving at the second stop, nor left the first stop with maximum petrol. If the cost of petrol at the previous refueling is better than the cost of petrol at the current location, then we can purchase more fuel at the previous location, and less at the current, until either the old location leaves at capacity, or the new location is no longer being fueled. Otherwise, the new cost of petrol is better at the new location, in which case there is no point in arriving at the location with spare petrol. We can reduce the fuel bought at the previous location and increase fuel bought at the current location until either no fuel is bought at the previous location, or we arrive at the current location with 0 petrol. In both cases, we've either started following the rule above, or removed a location for buying fuel. Repeating this for all fueling locations, we can guarantee a complete path that spends optimally will follow this rule. As such, we know that an optimal path through the graph can be made that only does the following transitions: It goes from a town with 0 petrol, to the same town, but at max capacity (It can completely fill up) It goes from a town with 0 petrol, to another town with 0 petrol (Fueling at the previous town, arriving with 0 petrol) It goes from a town with maximum capacity petrol, to another town that is exactly "capacity" distance away (Arriving with 0 petrol) It goes from a town with maximum capacity petrol, to another town, where it then buys back up to capacity (Coming from a location with maximum capacity) * It goes from a town with maximum capacity petrol, to another town, buys some fuel, then arrives at another town with 0 petrol (Three fueling positions, A is at capacity, and C is arrived at with 0 petrol) By squishing that last scenario into a single edge, we can ensure that the only states that need to be represented in the graph are being at a town with 0 petrol, and at a town with capacity petrol. Another way to view this is that we will never leave a town with less than capacity petrol, and arrive at another town with more than 0 petrol. So the intermediary amounts of petrol are only ever used as a transitory position between a maximum capacity state, and a 0 state. As such, we can use Floyd-Warshall's algorithm to first compute the all-pairs shortest path between possible fueling locations, and then use this to generate the edges in our real graph. We'll have ~2n~ nodes, one to represent a 0L town, and another to represent a maximum capacity town. Then we can just create edges in the graph matching our dot-points above, and run floyd-warshall again. @code_include[solutions/main.cpp]{langs: "py,cpp", rm_config: True}