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;
                    }