This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

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



Read the problem.