Swiggy: Multi-Drop Delivery Optimization
Swiggy's success hinges on efficient delivery logistics. As a delivery agent, optimizing routes is crucial, especially when handling multiple orders simultaneously. This problem challenges you to find the fastest possible route for a single delivery agent tasked with picking up items from various restaurants and delivering them to their respective customers.
Your task is to implement a function that calculates the minimum total time required for a delivery agent to complete all assigned orders. The agent starts at a given startLocation and must pick up each order's item from its pickupLocation before delivering it to its dropoffLocation. The agent can carry multiple items at once.
Specifically, you need to:
pickupLocation and dropoffLocation.pickupLocations (for items not yet picked up) and then all dropoffLocations (for items already picked up), ensuring each item is picked up before it's delivered.Function Signature:
function findMinDeliveryTime(n: number, roads: number[][], startLocation: number, orders: number[][]): number
n: An integer representing the total number of locations in the city, indexed from 0 to n-1.roads: A number[][] where each inner array [u, v, time] represents an undirected road between location u and location v that takes time minutes to travel. There might be multiple roads between the same pair of locations; the shortest one should be considered.startLocation: An integer representing the agent's initial location.orders: A number[][] where each inner array [pickupLocation, dropoffLocation] represents an order. pickupLocation is the restaurant and dropoffLocation is the customer's address. The agent must pick up the item at pickupLocation before delivering it to dropoffLocation.Return Value:
[u, v, time] exists, you can travel from u to v or v to u in time minutes.startLocation after completing all deliveries.Examples
Example 1
Input:
n = 4, roads = [[0,1,10],[1,2,20],[2,3,10]], startLocation = 0, orders = [[1,3]]
Output:
40
Note:
Agent starts at 0. Path: 0 -> 1 (pickup order 0, time=10). At 1, item picked. Path: 1 -> 2 -> 3 (dropoff order 0, time=20+10=30). Total time = 10 + 30 = 40.
Example 2
Input:
n = 5, roads = [[0,1,10],[1,2,5],[2,3,10],[3,4,5],[0,4,30]], startLocation = 0, orders = [[1,3],[2,4]]
Output:
25
Note:
Agent starts at 0. APSP (shortest path between any two locations): 0 1 2 3 4 0: 0 10 15 25 20 1:10 0 5 15 10 2:15 5 0 10 5 3:25 15 10 0 5 4:20 10 5 5 0
Optimal path: 0 -> 1 (pickup order 0, time=10). State: (loc=1, p_mask=0b01, d_mask=0b00). Then 1 -> 2 (pickup order 1, time=5). State: (loc=2, p_mask=0b11, d_mask=0b00). Total time=15. Then 2 -> 4 (dropoff order 1, time=5). State: (loc=4, p_mask=0b11, d_mask=0b10). Total time=20. Then 4 -> 3 (dropoff order 0, time=5). State: (loc=3, p_mask=0b11, d_mask=0b11). Total time=25. All orders delivered in 25 minutes.
Example 3
Input:
n = 3, roads = [[0,1,5],[1,2,5]], startLocation = 0, orders = [[0,2]]
Output:
10
Note:
Agent starts at 0. At location 0, order 0 is picked up (instantaneous). State: (loc=0, p_mask=0b01, d_mask=0b00). Path: 0 -> 1 -> 2 (dropoff order 0, time=5+5=10). State: (loc=2, p_mask=0b01, d_mask=0b01). Total time = 10.
Constraints
1 <= n <= 500 <= roads.length <= n * (n - 1) / 20 <= u, v < n, u != v1 <= time <= 10000 <= startLocation < n1 <= orders.length <= 8 (Let M = orders.length)0 <= pickupLocation, dropoffLocation < npickupLocation != dropoffLocation for any order.0 to n-1.N and M values.Loading editor...