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