Your question is Shortest Path for Delivery Batch. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
A DoorDash delivery batch is represented by a weighted directed graph. Each vertex is a location, and each edge contains the travel time between two locations. Starting from a given location, find the minimum-time route that visits every required delivery location in any order.
Return the route as an ordered list of locations and its total travel time. If no route can visit all delivery locations, return ([], -1).
Implement shortest_batch_route(graph, start, deliveries).
graph is a dictionary mapping each location to a list of [neighbor, travel_time] pairs.start is a location identifier present in the graph.deliveries is a list of distinct location identifiers.[route, total_time], where route starts at start and contains every delivery location exactly at least once. Intermediate locations may repeat.The route must be globally optimal. It is not enough to choose the nearest undelivered stop at each step.
def shortest_batch_route(graph, start, deliveries):