Untitled

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

const int INF = numeric_limits<int>::max();
int n;
vector<vector<int>> graph;
vector<vector<int>> dp;

int tsp(int mask, int pos) {
    if (mask == (1 << n) - 1) {
        return graph[pos][0];
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int minCost = INF;

    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            int newCost = graph[pos][city] + tsp(mask | (1 << city), city);
            minCost = min(minCost, newCost);
        }
    }

    return dp[mask][pos] = minCost;
}

int main() {
    cout << "Enter number of cities: ";
    cin >> n;

    graph.assign(n, vector<int>(n));
    dp.assign(1 << n, vector<int>(n, -1));

    cout << "Enter adjacency matrix (0 for self-loops, other values for distances):\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    int minCost = tsp(1, 0);
    cout << "Minimum cost for TSP: " << minCost << endl;

    return 0;
}