FastPrep
Problem · Graph

Minimum Fuel Cost Between Cities

Learn this problem
● HardMicrosoft logoMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

There are n cities connected by undirected roads. Each road [u, v, distance] consumes distance units of fuel. Fuel costs fuelPrices[i] per unit in city i.

You start in start with an empty, unlimited-capacity fuel tank. At any visited city, you may buy any nonnegative amount of fuel before taking another road. Return the minimum total cost required to reach destination, or -1 if it is unreachable.

Function

minFuelCost(n: int, roads: int[][], fuelPrices: int[], start: int, destination: int) → long

Examples

Example 1

n = 3roads = [[0,1,3],[1,2,6]]fuelPrices = [5,2,9]start = 0destination = 2return = 27

Buy 3 units at city 0 for 15, then 6 units at city 1 for 12. The total is 27.

Example 2

n = 4roads = [[0,1,5],[0,2,1],[2,1,1],[1,3,2],[2,3,10]]fuelPrices = [10,8,2,9]start = 0destination = 3return = 16

Travel 0 -> 2 -> 1 -> 3. The first unit costs 10; after reaching city 2, the remaining three units cost 2 each.

Constraints

  • 1 <= n <= 200
  • 0 <= roads.length <= 2 * 10^4
  • Every road has two distinct valid endpoints and a positive distance.
  • 1 <= fuelPrices[i] <= 10^6
  • 0 <= start, destination < n

More Microsoft problems

drafts saved locally
public long minFuelCost(int n, int[][] roads, int[] fuelPrices, int start, int destination) {
    // Your code here
}
n3
roads[[0,1,3],[1,2,6]]
fuelPrices[5,2,9]
start0
destination2
expected27
checking account