P29 · 2 seconds · 256 MB
Traveling Salesman
`dist` is an `n×n` matrix of non-negative edge weights. Return the minimum cost of a cycle that starts at city `0`, visits every city **exactly once**, and returns to `0`. `n` is at least 1. For `n = 1` the answer is `0` (already there; no need to travel). The matrix is not necessarily symmetric.
function tsp(dist) → number
CONSTRAINTS
- 1 ≤ n ≤ 10
- dist.length === n and every row has length n
- 0 ≤ dist[i][j] ≤ 10⁴
- dist[i][i] = 0
Input: dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
Output: 80
0→1→3→2→0 costs 10+25+30+15 = 80.
Input: dist = [[0]]
Output: 0
1
2
3
4
5
6
7
8
Arena judges JavaScript in a Web Worker (1s wall-clock, then TLE). Samples are public; submit runs hidden tests too. C++/Python is a later swarm package.