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 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 i = 0; i < n; i++){
            if(mask & (1 << i)){
                for (int j = 0; j < n; j++){
                    if(!(mask & (1 << j))) {
                        dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + cost[i][j]);
                    }
                }
            }
        }
    }
    
    int ans = INF;
    for (int i = 0; i < n; i++){
        ans = min(ans, dp[N-1][i] + cost[i][0]);
    }
    cout << ans << "\n";
    return 0;
}