# Variation of the gas station problem

Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $$u$$ the car refuels an amount equal to $$F(u)$$ of fuel. The car cannot traverse an edge if it doesn't have enough fuel to do so. Consider that the car has to travel from city $$s$$ to city $$t$$, and starts his travel with an amount equal to $$F_0$$ of fuel. Find the path in which the car reaches $$t$$ with the most amount of fuel left.

For solving this problem I created a copy $$G'$$ of the original graph. Starting from node $$s$$ I traverse the whole graph and remove the edges in which it is not possible for the car to traverse the edge because it would run out of fuel. Then, I create a copy $$G''$$ of $$G'$$ in which its edges are the original weight plus the amount of fuel the car charges when getting to the ending node of the edge. Finally, running the Bellman-Ford or Dijkstra's algorithm on $$G''$$ but with the weights multiplied by $$-1$$ would get me the answer. Is this answer correct of is there a more efficient way?

• Don't run Dijkstra, it doesn't deal well with negative edges Oct 12 at 5:32
• A previous question can be seen as the same as this question. Please see my hint for a more efficient way over there. Oct 13 at 10:18