Minimum Cost to Travel from City A to City B - Microsoft (L60 SWE)

Problem Preview

"A country consists of cities connected by bidirectional roads. Each road has a fuel requirement equal to its weight. You are given: - An array `arr`, where `arr[i]` denotes the fuel price per unit in city `i`. - A road network connecting cities. - A source city `A`. - A destination city `B`. Your truck has: - Infinite fuel tank capacity. - Ability to buy any amount of fuel at any city. Find the minimum cost required to travel from city `A` to city `B`. If no path exists, return `-1`. ### Example Fuel Prices: `arr = [9, 11, 3, 2, 10]` Suppose the optimal route is: `3 → 5 → 1 → 4 → 2` Strategy: 1. Buy fuel at City 3 (price = 3) sufficient to reach City 4. 2. At City 4 (price = 2), purchase remaining fuel needed to reach destination. 3. Since fuel can be stored indefinitely, buying more at cheaper cities reduces overall cost. Output: `27`"