You have n warehouses and n shops. At each warehouse, a truck is loaded with enough goods to supply one shop. There are m roads, each going from a warehouse to a shop, and driving along the ith road takes d i hours, where d i is an integer. Design a polynomial time algorithm to send the trucks to the shops, minimising the time until all shops are supplied.

Split the routes according to their categorization
Assuming that mid = di of the middle road, low = road with the least di, and high = road with the highest di, we may do a binary search on the sorted list.
All shops must be approachable only using these roads for every road, from low to mid.
Check if all shops can be reached from[tex]\bold{ low \ to\ mid+1}[/tex] using only these roads.
There is a solution if every shop can be reached by road only up to [tex]\bold{mid+1}[/tex], but not up to mid.
You can [tex]\bold{set \ low = mid+1}[/tex] if all businesses aren't accessible using both [tex]\bold{mid\ and\ mid+1}[/tex] roads.
If every shop could be reached using both mid and mid+1, then set high to mid-1.
With these layouts of businesses and roads, no response can be given because [tex]\bold{ low > high}[/tex]
You can do this by [tex]\bold{set\ mid = \frac{(low + high)}{2}}[/tex]
The new low, mid, and high numbers are used in step (a).

In a minimum amount of time, this algorithm will determine the best strategy to supply all shops.

Learn more:

polynomial-time algorithm: brainly.com/question/20261998