One rider, too many orders
A rider has a limited number of minutes. Each order is a round trip from the café that pays a tip. Compute travel times with Dijkstra, then choose orders with a knapsack so the rider earns the most within the shift.
Two algorithms, one plan
The problem splits cleanly in two. First, how long does each delivery take? That's a shortest-path question on a weighted road map: run Dijkstra once from the café, and each order's cost is twice the travel time (there and back). Second, which orders fit in the shift for the most tips? That's a 0/1 knapsack with minutes as weight and tips as value.
- Dijkstra from "Cafe" once — every destination's time.
- Order cost = 2 × time; skip unreachable destinations.
- Knapsack over orders with capacity = shift minutes.
- Trace back to list the chosen order ids, sorted.
Solve and test each half separately before connecting them.