Обход всех городов за минимальную стоимость

Дано n городов и матрица стоимостей dist размера n×n, где dist[i][j] — стоимость переезда из города i в город j. Нужно посетить каждый город ровно один раз, начав с любого города и закончив в любом (возвращаться в начальный город не требуется). Верните минимальную суммарную стоимость такого маршрута. Матрица может быть несимметричной: dist[i][j] и dist[j][i] могут различаться. Для n = 1 ответ равен 0. Перебор всех n! маршрутов не уложится в ограничения. Известно решение за O(2^n · n²) — попробуйте описать состояние парой «какие города уже посещены» и «в каком городе мы сейчас».