У тебя WA, потому что состояние динамики выбрано неверно.

Сейчас у тебя хранится:

• ans[mask] — минимальная стоимость пройти города из mask
• lst[mask] — последний город в этом оптимальном пути

И ты считаешь, что этого хватает. Но не хватает.

В чем ошибка

Для такой задачи надо различать:

• какие города уже посещены
• в каком городе ты сейчас находишься

То есть правильное состояние:

$$dp[mask][v]$$

где mask — множество посещённых городов, v — последний город.

---

Почему dp[mask] без последней вершины ломается

Потому что для одного и того же множества городов могут быть:

• путь дешевле, но заканчивается в “неудобном” городе
• путь чуть дороже, но заканчивается в “удобном” городе, из которого дальше сильно выгоднее продолжать

А ты оставляешь только один вариант через lst[mask] и выбрасываешь остальные. Из-за этого оптимальный глобальный путь может потеряться.

---

Пример идеи

Пусть для некоторой маски:

• лучший путь до mask стоит 10 и заканчивается в A
• второй путь стоит 11 и заканчивается в B

Если потом:

• из A в новый город ехать за 100
• из B в новый город ехать за 1

то:

• через A получится 110
• через B получится 12

Оптимум — через второй путь, но твой код его уже выкинул.

---

Что нужно делать

Нужно обычное DP по подмножествам:

• dp[mask][v] — минимальная стоимость попасть в v, посетив ровно mask
• старт: dp[1][0] = 0, потому что начинаем в городе 1
• переход:

  cpp
  dp[mask | (1 << to)][to] = min(dp[mask | (1 << to)][to],
                                 dp[mask][v] + a[v][to])

---

Ещё одно замечание

Вот это:

cpp
int a[n][n];

в C++ не стандартно. У некоторых компиляторов проходит как расширение, но лучше писать:

cpp
vector<vector<int>> a(n, vector<int>(n));

Это не причина WA, но лучше исправить.

---

Правильное решение

cpp
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    int FULL = 1 << n;
    vector<vector<int>> dp(FULL, vector<int>(n, INF));
    vector<vector<int>> parMask(FULL, vector<int>(n, -1));
    vector<vector<int>> parLast(FULL, vector<int>(n, -1));

    dp[1][0] = 0; // стартуем из города 1

    for (int mask = 1; mask < FULL; mask++) {
        if ((mask & 1) == 0) continue; // маршрут должен содержать город 1
        for (int v = 0; v < n; v++) {
            if (!(mask & (1 << v))) continue;
            if (dp[mask][v] == INF) continue;

            for (int to = 0; to < n; to++) {
                if (mask & (1 << to)) continue;
                if (a[v][to] == 0) continue;

                int nmask = mask | (1 << to);
                int nd = dp[mask][v] + a[v][to];
                if (nd < dp[nmask][to]) {
                    dp[nmask][to] = nd;
                    parMask[nmask][to] = mask;
                    parLast[nmask][to] = v;
                }
            }
        }
    }

    int fullMask = FULL - 1;
    int best = INF, last = -1;

    for (int v = 0; v < n; v++) {
        if (dp[fullMask][v] < best) {
            best = dp[fullMask][v];
            last = v;
        }
    }

    if (best == INF) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> path;
    int mask = fullMask;
    while (last != -1) {
        path.push_back(last);
        int pm = parMask[mask][last];
        int pv = parLast[mask][last];
        mask = pm;
        last = pv;
    }

    reverse(path.begin(), path.end());

    cout << best << '\n';
    for (int v : path) {
        cout << v + 1 << ' ';
    }
    cout << '\n';

    return 0;
}

---

Сложность

Для N <= 17 это нормально:

• состояний: 2^N * N
• переходов: 2^N * N * N

То есть примерно:

$$O(2^N \cdot N^2)$$

для 17 проходит.

---

Коротко: почему именно у тебя WA

Потому что ты пытаешься решить задачу гамильтонова пути через dp[mask], а нужно через dp[mask][last].
Иначе теряется информация о том, в каком городе закончился путь.

Могу ещё показать маленький контрпример именно к твоему подходу, на котором он даёт неверный ответ.

Окей, давай разберём DP по подмаскам максимально понятно и “с нуля”, без магии.

---

🔷 1. Что такое “подмаска”

Если N ≤ 17, удобно кодировать множество городов числом (битовой маской):

• есть N городов → N битов
• если город i посещён → бит i = 1

Пример (n = 4):

mask = 0101₂ = 5

Это значит: посещены города 0 и 2

---

🔷 2. Идея DP по подмаскам

Мы перебираем все подмножества городов и считаем ответ для каждого.

В задачах типа TSP (как у тебя):

👉 важно не только какие города посещены, но и где мы сейчас

---

🔷 3. Правильное состояние

$$dp[mask][v]$$

• mask — какие города уже посещены
• v — в каком городе мы сейчас
• значение — минимальная стоимость

---

🔷 4. База

Стартуем из города 1 (индекс 0):

cpp
dp[1 << 0][0] = 0;

То есть:

• посещён только город 1
• стоим в нём
• стоимость = 0

---

🔷 5. Переход (самое главное)

Мы пытаемся добавить новый город to:

cpp
if (!(mask & (1 << to))) // ещё не посещён

Переход:

$$dp[mask][v] \rightarrow dp[mask \cup \{to\}][to]$$

Код:

cpp
int newMask = mask | (1 << to);
dp[newMask][to] = min(
    dp[newMask][to],
    dp[mask][v] + a[v][to]
);

---

🔷 6. Полный цикл DP

cpp
for (int mask = 0; mask < (1 << n); mask++) {
    for (int v = 0; v < n; v++) {
        if (!(mask & (1 << v))) continue; // v не в mask
        if (dp[mask][v] == INF) continue;

        for (int to = 0; to < n; to++) {
            if (mask & (1 << to)) continue; // уже был
            if (a[v][to] == 0) continue;    // нет ребра

            int newMask = mask | (1 << to);
            dp[newMask][to] = min(
                dp[newMask][to],
                dp[mask][v] + a[v][to]
            );
        }
    }
}

---

🔷 7. Как получается ответ

Когда:

mask = (1 << n) - 1

это значит: посещены ВСЕ города

Берём минимум:

cpp
min(dp[fullMask][v])

---

🔷 8. Как восстанавливается путь

Храним родителей:

cpp
parMask[mask][v]
parLast[mask][v]

И идём назад:

cpp
while (...) {
    path.push_back(v);
    ...
}

---

🔷 9. Интуиция (самое важное)

Представь:

• ты строишь путь постепенно
• mask — какие города уже включены
• v — где ты сейчас стоишь

И ты говоришь:

👉 “Если я сейчас в v, то могу пойти в to”

---

🔷 10. Почему нельзя dp[mask] (как у тебя)

Потому что:

• один и тот же набор городов можно пройти разными способами
• но последний город влияет на будущее

👉 значит, состояние обязано включать last

---

🔷 11. Сложность

$$O(2^N \cdot N^2)$$

Для N ≤ 17 — нормально.

---

🔷 12. Мини-пример

text
города: 1,2,3

mask = 001 → {1}
mask = 011 → {1,2}
mask = 111 → {1,2,3}

DP строится так:

text
{1} → {1,2}
{1} → {1,3}
{1,2} → {1,2,3}
{1,3} → {1,2,3}

---

🔥 Итог

DP по подмаскам — это:

👉 перебор всех множеств
👉 хранение состояния “что уже выбрали”
👉 добавление одного элемента за шаг

---

Если хочешь, могу:

• разобрать твой код построчно
• или дать ещё 2–3 типовые задачи, где используется этот приём