Mr lee Samsung

/*

Mr. Lee has to travel various offices abroad to assist branches of each place. But he has a problem. The airfare would be real high as all offices he has to visit are in foreign countries. He wants to visit every location only one time and return home with the lowest expense. Help this company-caring man calculate the lowest expense.

Time limit : 1 second (java : 2 seconds)
Input format
Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row. N, the number of offices to visit is given on the first row per each test case. At this moment, No. 1 office is regarded as his company (Departure point). (1 ≤ N ≤ 12) Airfares are given to move cities in which branches are located from the second row to N number rows. I.e. jth number of ith row is the airfare to move from ith city to jth city. If it is impossible to move between two cities, it is given as zero.

Output format
Output the minimum airfare used to depart from his company, visit all offices, and then return his company on the first row per each test case.

Example of Input

2
5
0 14 4 10 20
14 0 7 8 7
4 5 0 7 16
11 7 9 0 2
18 7 17 4 0
5
9 9 2 9 5
6 3 5 1 5
1 8 3 3 3
6 0 9 6 8
6 6 9 4 8

Example of Output

30
18

*/

#include <iostream>
using namespace std;

int n;
int a[20][20];
int dp[4096][12];
int visited_all= (1<<12) - 1;

int minCost(int mask,int pos){
    if(mask==visited_all)
        return a[pos][0];

    if(dp[mask][pos]!=-1) return dp[mask][pos];

    int ans=99999;
    for(int city=0; city<n; city++){
        if((mask& (1<<city))==0 && a[pos][city]!=0) {
            // cout<<a[pos][city]<<" ";
            int newAns= a[pos][city] + minCost(mask | (1<<city), city);
            ans=min(ans,newAns);
        }
    }
    return dp[mask][pos] = ans;
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        visited_all= (1<<n) -1;

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>a[i][j];

        for(int i=0; i<4096; i++)
            for(int j=0; j<12; j++)
                dp[i][j]=-1;

        int ans=minCost(1,0);
        cout<<ans<<endl;
    }
}