Myntra Delivery: Optimal Route with Fuel Constraints
Myntra relies on an efficient delivery network to get products to customers. Delivery agents navigate a complex city grid, where each road has a specific distance and consumes a certain amount of fuel. Optimizing routes is crucial for timely deliveries and cost efficiency. This problem challenges you to find the most optimal delivery path under realistic fuel constraints.
Your task is to implement a function that determines the shortest possible total distance for a delivery vehicle to travel from a startNode to an endNode. The vehicle begins with a fixed initialFuel capacity. It cannot traverse a road if its current fuel level is less than the fuelCost of that road. The goal is to minimize the total distance traveled while ensuring the vehicle never runs out of fuel mid-journey.
Function Signature:
function findOptimalRoute(n: number, edges: number[][], startNode: number, endNode: number, initialFuel: number): number
Parameters:
n: An integer representing the number of intersections in the city, labeled from 0 to n-1.edges: A 2D array of integers, where each edge[i] is [u, v, distance, fuelCost]. This indicates a bidirectional road between intersection u and intersection v with a given distance and fuelCost.startNode: An integer representing the starting intersection for the delivery.endNode: An integer representing the destination intersection for the delivery.initialFuel: An integer representing the total amount of fuel the vehicle starts with.Return Value:
endNode from startNode while respecting fuel constraints. If endNode is unreachable, return -1.[u, v, distance, fuelCost], you can travel from u to v or v to u with the same distance and fuelCost.initialFuel represents the maximum fuel capacity. You cannot exceed this capacity, and you cannot traverse an edge if the current fuel in your tank is less than the fuelCost of that edge.initialFuel capacity.Examples
Example 1
Input:
n = 3, edges = [[0,1,10,1],[1,2,10,1]], startNode = 0, endNode = 2, initialFuel = 5
Output:
20
Note:
Path 0 -> 1 -> 2: Total distance = 10 + 10 = 20. Total fuel consumed = 1 + 1 = 2. Since initialFuel (5) is sufficient (5 >= 2), this path is valid and optimal.
Example 2
Input:
n = 3, edges = [[0,1,10,1],[1,2,10,1],[0,2,30,5]], startNode = 0, endNode = 2, initialFuel = 1
Output:
-1
Note:
Path 0 -> 1 -> 2: Requires 2 fuel (1 for 0-1, 1 for 1-2). Initial fuel is 1, so 1-2 leg is impossible. Path 0 -> 2: Requires 5 fuel. Initial fuel is 1, so this path is impossible. No valid path exists.
Example 3
Input:
n = 4, edges = [[0,1,10,1],[1,2,10,1],[0,3,5,1],[3,2,5,3]], startNode = 0, endNode = 2, initialFuel = 3
Output:
20
Note:
Path 0 -> 1 -> 2: Distance = 10 + 10 = 20. Fuel consumed = 1 + 1 = 2. Remaining fuel after 0->1 is 2. Remaining fuel after 1->2 is 1. This path is valid. Path 0 -> 3 -> 2: Distance = 5 + 5 = 10. Fuel consumed = 1 + 3 = 4. After 0->3, 2 fuel remains. For 3->2, 3 fuel is needed, but only 2 is available. This path is invalid due to insufficient fuel for the 3->2 leg. Therefore, the only valid path is 0 -> 1 -> 2, with a distance of 20.
Constraints
2 <= n <= 1000 <= edges.length <= n * (n - 1) / 2 (maximum number of unique bidirectional edges)0 <= u, v < n, u != v for any edge.1 <= distance <= 1000 for any edge.1 <= fuelCost <= 100 for any edge.0 <= startNode, endNode < n0 <= initialFuel <= 500Loading editor...