Drone Delivery Optimization with Limited Boosts
In the rapidly evolving world of logistics, drone delivery networks are becoming crucial for efficient package transportation. A key challenge is optimizing delivery routes to minimize travel time while managing valuable resources. Our drone fleet has access to standard routes, but each drone is also equipped with a limited number of 'boosts' that can significantly reduce travel time on any segment. Your task is to design an algorithm to find the fastest possible route from a starting depot to a destination, leveraging these boosts strategically.
Implement the function minBoostedTravelTime that calculates the minimum time required for a drone to travel from a startNode to an endNode within a given network. The drone has a maximum of k boosts available to use across its entire journey. Each boost can be applied to exactly one segment of the path, reducing its travel time from time to boostTime.
Function Signature:
function minBoostedTravelTime(n: number, edges: number[][], startNode: number, endNode: number, k: number): number
Parameters:
n: An integer representing the total number of locations (nodes) in the network, indexed from 0 to n-1.edges: A 2D array of integers, where each inner array [u, v, time, boostTime] represents an undirected road segment between location u and location v. time is the normal travel duration, and boostTime is the travel duration if a boost is used on this segment.startNode: An integer representing the starting location of the drone.endNode: An integer representing the target destination of the drone.k: An integer representing the maximum number of boosts available for the entire journey.Return Value:
endNode from startNode using at most k boosts. If endNode is unreachable, return -1.time and boostTime values are positive integers.boostTime for any segment is always strictly less than its time.[u, v, time, boostTime], travel from v to u also takes time or boostTime.startNode equals endNode; in this case, the time is 0.Examples
Example 1
Input:
n = 3, edges = [[0,1,10,2],[1,2,5,1]], startNode = 0, endNode = 2, k = 1
Output:
7
Note:
Path 0 -> 1 (boosted) -> 2 (normal). Time: 2 + 5 = 7. (1 boost used) Path 0 -> 1 (normal) -> 2 (boosted). Time: 10 + 1 = 11. (1 boost used) Path 0 -> 1 (normal) -> 2 (normal). Time: 10 + 5 = 15. (0 boosts used) Minimum is 7.
Example 2
Input:
n = 4, edges = [[0,1,10,2],[0,2,20,5],[1,3,15,3],[2,3,8,1]], startNode = 0, endNode = 3, k = 2
Output:
5
Note:
Consider paths from 0 to 3:
Example 3
Input:
n = 2, edges = [[0,1,100,10]], startNode = 0, endNode = 1, k = 0
Output:
100
Note:
With 0 boosts, only the normal travel time applies: 100.
Example 4
Input:
n = 3, edges = [[0,1,10,2]], startNode = 0, endNode = 2, k = 1
Output:
-1
Note:
Node 2 is unreachable from node 0.
Constraints
1 <= n <= 1000 <= edges.length <= n * (n - 1) / 21 <= time, boostTime <= 1000 for any edge.boostTime < time for any edge.0 <= startNode, endNode < n0 <= k <= n(u, v).k=0, unreachable destination).Loading editor...