A Shortest path with fuel constraints

Question

I found this problem somewhere in a contest and haven't been able to come up with a solution yet. I am thinking on the lines of applying Dijkstra's or something but it is not very clear :

''You are given a weighted connected graph of cities with all edges having positive weights. Some of the cities ( nodes ) have petrol pump whereas some don’t. You have a bike with the tank capacity of C. That is, with full tank, the car can travel for C units of distance. At any city with a petrol pump the car can fill its tank to full. Find out the shortest path between the a given source and a given destination. Assume that you start with a full tank.''

I have a feeling O(mn logn) will be accepted by it.

Answer 1

Basically you need to split each node n_i to multi nodes base on the remaining fuel when bike arrived, let's call it (n_i, r). You don't need to create all (n_i, r) at the beginning, you can do it on fly.

Then similar to Dijkstra, you start from node (n_0, C), each time you can find next (n_x, r) you can reach with the smallest distance. And update all the nodes (n_y, ry) connected to (n_x, r). ry will be reset to C if n_y has a pump. And if for n_y, there is already a node (n_y, r) and r >= ry, then you don't need to create new node (n_y, ry), just ignore it.

I can not say the runtime complexity, but it should be good enough to get AC in the contest.

Answer 2

@Tim Green's method will create an exponential (in the number of gas stations) number of nodes. Running Dijkstra's over that will be very slow. There is a much faster way.

---

First, find the distances between all the gas stations. Also include the distances from the source to each gas station, from each gas station to the finish, and from the source to the finish. This can be done by running Dijkstra's multiple times.

This will give you a graph of all possible valid routes from start to finish. Simply run Dijktra's one more time over this graph to get the final solution.

Since each run of Dijkstra's will be O(V²) (V = number of cities) and you must run it O(G) times (G = number of gas stations, one run of Djikstra can find distance from one gas station to all other gas-stations), this algorithm will run in O(V²G) time.