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\n0 10 15 20\n10 0 35 25\n15 35 0 30\n20 25 30 0

Output:
80

Solution in C++


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

int main(){
    int n; cin >> n;
    vector<vector<int>> dist(n, vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> dist[i][j];
        }
    }
    int N = 1 << n;
    vector<vector<int>> dp(N, vector<int>(n, 1e9));
    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] + dist[u][v]);
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for(int u=0; u<n; u++){
        ans = min(ans, dp[N-1][u] + dist[u][0]);
    }
    cout << ans;
    return 0;
}