Problem 48: Travelling Salesman Problem
Problem Statement: Given a complete directed graph with n nodes (n <= 16) and a cost matrix, compute the minimum tour cost that visits every node exactly once and returns to the starting node.
Input
The first line contains an integer n. Each of the next n lines contains n space-separated integers representing the cost matrix.
Output
Print the minimum tour cost.
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 dynamic programming where dp[mask][i] stores the minimum cost to visit a set of nodes (mask) and end at node i, then combine the results to form a full tour.
Method 2: For very small n, a brute-force permutation approach would work, but bitmask DP achieves exponential time reduction.
Solution in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
const int INF = 1e9;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> cost(n, vector<int>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> cost[i][j];
}
}
int N = 1 << n;
vector<vector<int>> dp(N, vector<int>(n, INF));
dp[1][0] = 0;
for(int mask = 1; mask < N; mask++){
for(int u = 0; u < n; u++){
if(mask & (1 << u)){
for(int v = 0; v < n; v++){
if(!(mask & (1 << v))) {
dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + cost[u][v]);
}
}
}
}
}
int ans = INF;
for(int u = 0; u < n; u++){
ans = min(ans, dp[N - 1][u] + cost[u][0]);
}
cout << ans << " ";
return 0;
}