Problema del Viajante de Comercio

Dado un grafo completo con n ciudades y una matriz de distancias distances donde distances[i][j] es el costo de viajar de la ciudad i a la ciudad j, encuentra el costo mínimo del ciclo hamiltoniano: el recorrido que visita todas las ciudades exactamente una vez y regresa a la ciudad de inicio (ciudad 0).

Ejemplo

Para n = 4 ciudades:

El tour óptimo es 0 → 1 → 3 → 2 → 0 con costo 10 + 25 + 30 + 15 = 80.

tsp([[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]])  # 80
tsp([[0,5],[5,0]])  # 10
tsp([[0]])  # 0

Notas

• La matriz es simétrica: distances[i][j] == distances[j][i]
• distances[i][i] == 0 siempre
• El ciclo siempre empieza y termina en la ciudad 0
• Para n = 1, el costo es 0

Restricciones: 1 ≤ n ≤ 15

Pista

Considera usar programación dinámica con bitmask: define dp[mask][i] como el costo mínimo de visitar exactamente las ciudades representadas por mask, terminando en la ciudad i. La complejidad es O(2ⁿ · n²).