Minimize Fuel Cost Across Cities

Problem Statement

You are planning a road trip across a network of n cities labeled from 0 to n - 1. You are given an undirected weighted graph represented by edges, where edges[i] = [u, v, dist] indicates a bidirectional road between city u and city v requiring dist units of fuel to traverse.

Each city has a gas station with a specific fuel price given in the array prices, where prices[i] is the price per unit of fuel at city i. Your vehicle has an unlimited fuel tank capacity, meaning you can purchase and store as much fuel as you want at any city you visit. You start at city start with an empty fuel tank and must reach city target.

Because tank capacity is unlimited, any fuel used along an edge u -> v is optimally purchased at the cheapest city visited on or before city u along your route.

Return the minimum total fuel cost to travel from start to target. If target is unreachable from start, return -1.

Function Signature

def min_fuel_cost(n: int, edges: list[list[int]], prices: list[int], start: int, target: int) -> int:
    pass

Constraints

• 1 <= n <= 500
• 0 <= len(edges) <= 2000
• edges[i] = [u, v, dist] where 0 <= u, v < n, u != v, and 1 <= dist <= 10^4
• prices.length == n
• 1 <= prices[i] <= 10^4
• 0 <= start, target < n
• The graph may have multiple edges between the same pair of cities; you may assume all edge weights are positive.

Examples

Example 1

Input:
n = 3
edges = [[0, 1, 5], [1, 2, 10], [0, 2, 12]]
prices = [10, 2, 20]
start = 0
target = 2

Output: 70

Explanation:
Path 1 (direct): 0 -> 2
Fuel needed: 12. Cheapest station seen so far is city 0 (price 10).
Cost = 12 * 10 = 120.

Path 2: 0 -> 1 -> 2
- Edge 0 -> 1 (dist 5): Bought at city 0 (price 10) = 5 * 10 = 50.
- At city 1, fuel price is 2, which is lower than city 0.
- Edge 1 -> 2 (dist 10): Bought at city 1 (price 2) = 10 * 2 = 20.
Total cost = 50 + 20 = 70.

Example 2

Input:
n = 4
edges = [[0, 1, 4], [2, 3, 3]]
prices = [5, 4, 3, 2]
start = 0
target = 3

Output: -1

Explanation:
There is no path connecting city 0 and city 3.