Динамика по подмаскам

Информатика
1

Остап Бендер снова пытается получить причитающиеся драгоценности, но на этот раз они были заперты в шкатулке, для открытия которой необходимо иметь N ключей. По закономерной случайности каждый из ключей был спрятан в одном из N стульев, распроданных на недавнем аукционе. После аукциона эти стулья были развезены в N городов.

И вот теперь Остап решился на новую безумную затею: заехать в каждый из городов и, провернув в каждом из них аферу, выкрасть необходимые ключи. Чтобы избежать конфликтов с недоброжелателями, Остап не хочет больше одного раза появляться в каком-либо городе. Также у Остапа есть список цен за проезд между каждой парой городов. Изначально Остап находится в городе под номером 1 и после посещения всех городов может незаметно скрыться из этой страны.

Помогите Остапу найти порядок посещения городов, при котором ему потребуется потратить как можно меньше средств на странствия, и тогда, возможно, он поделится с Вами добытыми бриллиантами.
Формат входных данных

Первая строка содержит единственное число N — количество городов (1 ≤ N ≤ 17).

Следующие N строк содержат по N целых неотрицательных чисел. j-тое число в i-й строке означает стоимость проезда из города i в город j (0≤ a_{ij} ≤100). Если a_{ij} > 0, то проезд стоит a_{ij} рублей, иначе — это означает, что из города i в j невозможно проехать напрямую.
Формат результата

В первой строке выведите минимальную сумму денег, необходимую для посещения всех городов Остапом. В следующей строке выведите N чисел — порядок посещения городов, при котором эта сумма достигается. Если затею Остапа невозможно вывести, то в единственной строке выходного файла выведите число -1.
Есть код, скорее всего это динамика по подмаскам.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
ll mod = 1000000007;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> gr(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> gr[i][j];
        }
    }
    vector<vector<int>> dp((1 << n), vector<int>(n,-1)),pref((1 << n), vector<int>(n, -1));
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = 0;
        pref[1 << i][i] = i;
    }
    for (int mask = 2; mask < (1 << n); ++mask) {
        for (int p = 0; p < n; ++p) {
            if ((mask >> p) & 1) {
                for (int g = 0; g < n; ++g) {
                    if ((mask >> g) & 1 && g != p && gr[g][p] != 0) {
                        if ((dp[mask][p] == -1 || (dp[mask ^ (1 << p)][g] + gr[g][p] < dp[mask][p])) && dp[mask ^ (1 << p)][g]!=-1) {
                            dp[mask][p] = dp[mask^(1<<p)][g] + gr[p][g];
                            pref[mask][p] = g;
                        }
                    }
                }
            }
        }
    }
    if (dp[(1 << n) - 1][0] != -1) {
        cout << dp[(1 << n) - 1][0] << "\n";
        int mask = (1 << n) - 1, p = 0;
        while (mask != 0) {
            int p1 = pref[mask][p];
            cout << p + 1 << " ";
            mask = mask ^ (1 << p);
            p = p1;
        }
    }
    else {
        cout << -1;
    }
}

Идея такая dp[mask][i] - минимальная сумма при вершинах из маски, при этом путь оканчивается в вершине i. Пересчёт идёт через подмаску, которая не содержит i вершину, и все возможные конечные вершины, которые есть в подмаске. Массив pref хранит вершину, через которую мы пересчитали значение, поэтому через него можно восстановить путь. По идее ответ находится в dp[ (1 << n) - 1 ][ 0 ], т.к. нам нет разницы конечная она или начально, просто изменится порядок обхода вершин на противоположный. Данный код должен работать за O(n^{2}). Однако этот код по какой-то причине не работает. Он выдаёт неправильный ответ. Уже не один час пытаюсь найти ошибку, но всё тщетно. Помогите, пожалуйста.

1 лайк