850. Shortest Grand Tour
A courier company must send one van through n depots numbered 0 to n-1. The van starts at depot 0, drives to every other depot exactly once, and finally returns to depot 0. Roads are one-way priced: dist[i][j] is the toll for driving directly from depot i to depot j, and dist[j][i] may be different. Toll values may be zero, and dist[i][i] = 0.
Return the minimum total toll of such a round trip. If n = 1 the van never moves and the answer is 0. A direct road between any two different depots always exists.
Example 1
- Input:
- dist = [[0,4,9,5],[3,0,2,8],[7,6,0,1],[2,9,4,0]]
- Output:
- 9
- Explanation:
The cheapest round trip is 0 to 1 to 2 to 3 to 0 with total cost 9; every other order costs more because tolls differ by direction.
Example 2
- Input:
- dist = [[0,5,2],[5,0,1],[2,1,0]]
- Output:
- 8
- Explanation:
Both directions around the triangle cost 5 + 1 + 2 = 8, so 8 is the minimum.
Constraints
- 1 ≤ n ≤ 15, where n = dist.length and every row has n entries
- 0 ≤ dist[i][j] ≤ 106, dist[i][i] = 0
- The answer fits in a 32-bit signed integer
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(2^n * n^2)
- Space
- O(2^n * n)