E5209. Продавец аквариумов

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair

const int INF = (int)1e9;

int CountBits(int x)
{
    int c = 0;
    while(x)
    {
        c += x & 1;
        x >>= 1;
    }
    return c;
}

int DropKthBit(int x,int k)
{
    return x - (1<<k);
}

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

    freopen("aquarium.in","r",stdin);
    freopen("aquarium.out","w",stdout);

    int n;
    cin >> n;

    vector<vector<int> > g(n,vector<int>(n));

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

    vector<vector<int> > dp(1<<14,vector<int>(14,INF));

    int x;

    for(int mask = 1; mask < (1 << n); mask++)
    {
        if(CountBits(mask) == 1)
        {
            for(int i = 0; i < n; i++)
                if(mask & (1<<i))
                    dp[mask][i] = 0;
        }
        for(int i = 0; i < n; i++)
        {
            if(mask & (1<<i))
            {
                for(int j = 0; j < n; j++)
                {
                    if(!(mask & (1<<j)))
                    {
                        if(dp[mask|(1<<j)][j] > dp[mask][i] + g[i][j])
                        {
                            dp[mask|(1<<j)][j] = dp[mask][i] + g[i][j];
                        }
                    }
                }
            }
        }
    }

    int mn;

    mn = *min_element(dp[(1<<n)-1].begin(),dp[(1<<n)-1].end());

    cout << mn << "\n";

    int t = (1<<n) - 1;
    x = -1;

    for(int i = 0; i < n; i++)
    {
        if(dp[t][i] == mn)
        {
            x = i;
            break;
        }
    }

    int K = 0;

    while(t != 0 && K < n)
    {
        K++;
        cout << x + 1 << " ";
        for(int i = 0; i < n; i++)
        {
            if(dp[DropKthBit(t,x)][i] + g[i][x] == dp[t][x])
            {
                t = DropKthBit(t,x);
                x = i;
                break;
            }
        }
    }

    return 0;
}