Untitled
unknown
c_cpp
25 days ago
1.1 kB
2
Indexable
#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; }
Editor is loading...
Leave a Comment