Как решить задачу коммивояжёра (TSP) через ДП по битовой маске за O(2^n · n²)?

Классический Held–Karp. Состояние dp[mask][i] = минимальная стоимость пути, который начался в городе 0, посетил ровно множество городов mask и сейчас стоит в городе i (бит i обязательно установлен в mask).

Идея: бит в маске = «город уже посещён». Переход — пробуем, куда пойти дальше из i в ещё не посещённый j:

const long long INF = 1e18;
int n; // <= 18
long long dist[20][20];
vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));

dp[1][0] = 0; // стартуем в городе 0, посещён только он
for (int mask = 1; mask < (1 << n); ++mask)
  for (int i = 0; i < n; ++i) {
    if (dp[mask][i] == INF) continue;
    if (!(mask & (1 << i))) continue;
    for (int j = 0; j < n; ++j) {
      if (mask & (1 << j)) continue;        // j уже посещён
      int nmask = mask | (1 << j);
      dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + dist[i][j]);
    }
  }

long long ans = INF;
for (int i = 1; i < n; ++i)
  ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]); // замыкаем цикл в 0

Сложность: состояний $2^n \cdot n$, переход перебирает $n$ соседей → время $O(2^n \cdot n^2)$, память $O(2^n \cdot n)$. Для $n=18$ это $\approx 2.6 \cdot 8.5 \cdot 10^5 \approx 8.5 \cdot 10^7$ — заходит. Обязательно long long для стоимости, иначе сумма рёбер переполнит int.