Editorial for JDCC '16 Contest 4 P4 - Gas N Go
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
We only want to buy gas from the cheapest place that we visited so far. Since our tank is infinite, we don't have to choose how much gas to buy, but instead buy it when we need it. We can't prioritize based solely on cost of gas to reach a station, but also the cost to buy gas. This can be done with 2D Dijkstra's. Cache the shortest distance to reach a station with a given cheapest station visited. When calculating the cost of gas, use the cheapest place visited.
Time Complexity:
Comments