Problem 19: Traveling Salesman Problem (Bitmask DP)
Problem Statement: Given a complete graph with n nodes and distances between every pair, compute the minimum tour cost using bitmask dynamic programming.
Input
The first line contains n. Next n lines contain n integers each representing the distance matrix.
Output
Print the minimum cost to complete the tour starting and ending at node 0.
Examples
Input:
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
Output:
80
Solution Explanation
Method 1: Use bitmask DP where dp[mask][i] denotes the minimum cost to reach node i having visited nodes in mask; transition by adding a new node. Method 2: A brute-force enumeration of all permutations works for small values of n, but bitmask DP drastically reduces complexity.
Solution in C++
#include
#include
#include
#include
using namespace std;
int main(){
int n; cin >> n;
vector> dist(n, vector(n));
for(int i=0;i> dist[i][j];
}
}
int N = 1 << n;
vector> dp(N, vector(n, 1e9));
dp[1][0] = 0;
for(int mask=1; mask