Skip to content
RED SAGSkills
hard60 ptsdynamic-programminggraph

Shortest Delivery Loop

A courier leaves the depot (stop 0), must visit every other stop exactly once, and then return to the depot. cost[i][j] is the travel cost from stop i to stop j; it may differ from cost[j][i].

Return the minimum total cost of such a loop. With at most 13 stops, a dynamic programme over subsets of visited stops (bitmask DP) is fast enough, while trying every order is not.

Example 1

Input: cost = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
Output: 80
Explanation: 0 → 1 → 3 → 2 → 0 costs 10 + 25 + 30 + 15.

Example 2

Input: cost = [[0]]
Output: 0
Explanation: Only the depot: nothing to do.

Constraints

  • 1 <= cost.length <= 13
  • cost[i].length == cost.length
  • cost[i][i] == 0
  • 0 <= cost[i][j] <= 1000
Hint 1

Let dp[mask][last] be the cheapest way to start at the depot, visit exactly the stops in mask, and stand at last.

Hint 2

Extend each state by one unvisited stop; the answer closes the loop from the best last stop back to 0.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Data Scientist, AI Engineer (LLM & Generative AI), Mobile App Developer, Machine Learning Engineer

Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.