#include <vector>
#include <iostream>
#include <cstdio>
using namespace std;

struct TspData
{  
    int n; // število točk
    vector<int> d; // d[u * n + v] = dolžina povezave od u do v
    vector<int> f; // f[u << n | a] = rešitev podproblema, ko smo v točki u in so neobiskane še točke a
    enum { z = 0 }; // začetna točka

    // Reši podproblem, ko smo v tocki 'u' in so neobiskane še 
    // tiste točke, katerih biti so prižgani v številu 'a'.
    int Resi(int u, int a)
    {
        // Ali imamo rešitev tega podproblema že shranjeno?
        int r = f[u << n | a]; if (r >= 0) return r;
        // Ali smo obiskali že vse točke?
        if (a == 0) r = d[u * n + z]; 
        // Če ne, preizkusimo vsa možna nadaljevanja.
        else for (int v = 0; v < n; ++v) if ((a >> v) & 1)
        {
            // Poskusimo narediti korak u -> v in potem nadaljevati rekurzivno.
            if (d[u * n + v] < 0) continue; // Mogoče povezave u -> v sploh ni.
            int kand = Resi(v, a & ~(1 << v));
            if (kand < 0) continue; // Mogoče se poti od 'v' naprej ne da nadaljevati.
            kand += d[u * n + v];
            // Najboljšo rešitev si zapomnimo.
            if (r < 0 || kand < r) r = kand;
        }
        // Shranimo rezultat v tabelo 'f' in ga vrnimo.
        printf("Tsp(%d, %d) = %d\n", u, a, r);
        f[u << n | a] = r; return r; 
    }
};

int Tsp(int n, vector<int> d)
{
    TspData tsp; tsp.n = n; tsp.d = d; tsp.f.resize(n << n, -1);
    // Začnimo v točki 'z', vse ostale so še neobiskane.  
    return tsp.Resi(TspData::z, ((1 << n) - 1) & ~(1 << TspData::z));
}

// Možna izboljšava: ker je točka 'z' vedno obiskana, bo v vrednostih
// 'a', s katerimi imamo opravka, bit 'z' vedno ugasnjen, zato bi bilo
// za tabelo f dovolj že 'n << (n - 1)' elementov (verjetno je najlažje,
// če vzamemo z = n - 1).

int main()
{
    // Primer iz https://www.csd.uoc.gr/~hy583/papers/ch11.pdf :
    // A (2) B (8) D (3) C (3) E (5) A = 21.
    cout << Tsp(5, {
        -1,  2, -1, 12,  5,
         2, -1,  4,  8, -1,
        -1,  4, -1,  3,  3,
        12,  8,  3, -1, 10,
         5, -1,  3, 10, -1
    }) << endl;
    return 0;
}