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.
Best Answer
Let's split the optimal path at nodes with refueling stations. If we have a fixed list of pumps we must go through, it clearly makes no sense to take any but the shortest path between each consecutive pair (be it the part from the source to the first pump, between two pumps or from the last pump to the destination); with no refueling in between.
But we can actually compute the shortest no-refueling paths between the source, destination and all the pump-nodes in $O(nm\log n)$ total time by simply running Dijkstra's algorithm from each of these nodes; with the additional constraint that distances greater than $C$ are treated as "infinity" -- this corresponds to "no refuelling permitted, even in a pump-node".
Doing so will give us a new graph, consisting of just the "interesting" nodes (source, destination and pumps), whose distances are precisely the shortest paths we just found. Running one more, completely unrestricted Dijkstra on this graph yields the answer we seek.