## Minimize Fuel Cost Across Cities ### Problem Hackerland has `g_nodes` cities numbered from `1` through `g_nodes` and bidirectional roads. Road `i` connects `g_from[i]` and `g_to[i]` and consumes `g_weight[i]` units of fuel. One unit of fuel costs `fuel_price[c - 1]` in city `c`. A vehicle starts in `start` with zero fuel and has unlimited tank capacity. At every visited city it may buy any nonnegative integer amount of fuel, and unused fuel can be carried across later roads. Determine the minimum total purchase cost needed to reach `destination`. Return `-1` if no route exists. ### Function Contract ```text get_min_cost(g_nodes, g_from, g_to, g_weight, fuel_price, start, destination) -> minimum_cost ``` - All graph and price inputs are JSON integers or arrays of JSON integers. - The three road arrays have the same length `g_edges`. - Parallel roads are allowed; self-loops are not present. - Return one JSON integer, or `-1` when `destination` is unreachable. - Do not mutate any input array. ### Examples ```text g_nodes = 5 g_from = [4, 5, 5, 1, 3, 4, 4] g_to = [1, 3, 4, 5, 1, 2, 3] g_weight = [1, 1, 8, 1, 3, 9, 5] fuel_price = [9, 11, 3, 2, 10] start = 3 destination = 2 result = 27 ``` One optimal route is `3 -> 5 -> 1 -> 4 -> 2`. Buy `3` fuel units at city `3` for `9`, then `9` units at city `4` for `18`. ```text g_nodes = 3 g_from = [1] g_to = [2] g_weight = [7] fuel_price = [5, 1, 4] start = 1 destination = 3 result = -1 ``` ```text g_nodes = 2 g_from = [1] g_to = [2] g_weight = [100] fuel_price = [7, 1] start = 2 destination = 2 result = 0 ``` ### Constraints - `1 <= g_nodes <= 300`. - `0 <= g_edges <= 3,000`. - `1 <= g_from[i], g_to[i] <= g_nodes`. - `1 <= g_weight[i] <= 1,000,000`. - `fuel_price.length == g_nodes`. - `1 <= fuel_price[i] <= 1,000,000`. - `1 <= start, destination <= g_nodes`. - Every finite minimum cost is at most `9,000,000,000,000,000`, so it is exact in signed 64-bit arithmetic and JavaScript safe integers. - Target `O(g_nodes * (g_nodes + g_edges) * log(g_nodes^2))` time or better and `O(g_nodes^2 + g_edges)` space. ```hint Remember the cheapest city already reached After following a path prefix, the cost of fuel for a later road may depend on an earlier city rather than only on the current city. ``` ### Discussion Requirements 1. Explain why ordinary shortest path using `road_weight * fuel_price[current_city]` can overpay when fuel can be carried. 2. Identify the extra state needed in addition to the current city. 3. Explain why a lower fuel price seen on a path can make one arrival at the same city dominate another. 4. State why breadth-first search is insufficient when transition costs differ. 5. Show how the unreachable and `start == destination` cases are handled.