Problem statement
A car is traveling in a directed graph from point $$$A$$$ to point $$$B$$$. Its fuel tank has a capacity of $$$F$$$. Traveling along an edge takes $$$1$$$ unit of time, and will burn $$$1$$$ unit of fuel. The car starts with a full tank of fuel. Some of the vertices in the graph are gas stations where the car can refuel. Refueling takes $$$1$$$ unit of time. What is the minimum time to travel from $$$A$$$ to $$$B$$$ (if it is possible at all).
The best I can come up with
Make a new graph where every vertex is a combination of the vertex in the original graph, and the remaining fuel in the tank: $$$vertex_{new-graph} = (vertex, fuel)$$$. For every edge in the original graph, add a corresponding edge in the new graph. If the original vertex is a gas station then we have to add 2 edges (one corresponding to refueling, and one corresponding to not refueling). We can now do a BFS which will take $$$O(V_{new-graph} + E_{new-graph})$$$ time which equals $$$O(V * F + E)$$$.
Is there a better solution?
