Minimum Delivery Cost Between Cities
Implement minimum_delivery_costs(delivery_charges, queries).
There are n cities indexed from 0 to n - 1, and city i has value delivery_charges[i]. A delivery can move from any city i to any different city j:
-
The normal move cost is
abs(delivery_charges[i] - delivery_charges[j])
.
-
If
j
is the unique city whose value is closest to city
i
's value, the move from
i
to
j
instead costs
1
.
-
If two or more cities tie for closest to
i
, city
i
has no discounted move.
A route may use intermediate cities. For each (start, end) query, return the minimum total cost to reach end from start.
Constraints
-
2 <= n <= 2,000
-
All delivery charges are distinct signed 32-bit integers.
-
1 <= len(queries) <= 2,000
-
Query endpoints are valid city indices.
-
Costs fit in signed 64-bit integers.
Candidate clarifications
Confirm whether closest-city ties disable the discount, whether the cheap edge is directed, and whether routes may visit intermediate cities.