Code : Travel Salesman Tour

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

const int inf = (int)1e8;

class Graph {
  public:
    int n;
    vector<vector<int>> d;
    vector<int> node_cost;

    Graph(int n) {
        this->n = n;
        d.resize(n, vector<int>(n, inf));
        node_cost.resize(n);
    }

    int tsp() {
        int full_mask = (1 << n) - 1;
        vector<vector<int>> dp(n, vector<int>(full_mask + 1, inf));

        // WLOG, Consider the first node as the start of the cycle.
        dp[0][1 << 0] = 0;

        for (int cnt = 0; cnt <= n; cnt++) {
            for (int mask = 0; mask <= full_mask; mask++) {
                if (__builtin_popcount(mask) != cnt) {
                    continue;
                }

                for (int i = 0; i < n; i++) {
                    if (((1 << i) & mask) == 0) {
                        continue;
                    }
                    for (int j = 0; j < n; j++) {
                        if ((1 << j) & mask) {
                            continue;
                        }
                        int nxt = mask | (1 << j);
                        dp[j][nxt] = min(dp[j][nxt], dp[i][mask] + d[i][j]);
                    }
                }
            }
        }

        int ans = inf;
        for (int i = 1; i < n; i++) {
            ans = min(ans, dp[i][full_mask] + d[i][0]);
        }
        return ans;
    }
};

void solve() {
    int n;
    cin >> n;
    Graph g(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cost;
            cin >> cost;
            if (cost == 0) {
                cost = inf;
            }
            g.d[i][j] = cost;
        }
    }
    cout << g.tsp() << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}