title: Suggest an algorithm (graph - possibly NP-Complete)
body: <p>There is a network of towns, connected by roads of various integer lengths.</p>
  
  <p>A traveler wishes to travel in his car from one town to another. However, he does not want to minimize distance traveled; instead he wishes to minimize the petrol cost of the journey. Petrol can be bought in any city, however each city supplies petrol at various (integer) prices (hence why the shortest route is not necessarily the cheapest). 1 unit of petrol enables him to drive for 1 unit of distance.
  His car can only hold so much petrol in the tank, and he can choose how many units of petrol to purchase at each city he travels through. Find the minimum petrol cost.</p>
  
  <p>Does anyone know an efficient algorithm that could be used to solve this problem? Even the name of this type of problem would be useful so that I can research it myself! Obviously it's not quite the same as a shortest path problem. Any other tips appreciated!</p>
  
  <p>EDIT - the actual problem I have states that there will be &lt;1000 cities; &lt;10000 roads; and the petrol tank capacity will be somewhere between 1 and 100.</p>