//状态压缩例题:最短Hamilton路径
//
//
//题目分析:
// 
//1<=n<=20,当n=20,用暴力做法一共有20的阶乘条路径,同时维护每条路径的时间复杂度为20,所以暴力做法的时间复杂度为20的阶乘乘以20,远远超出要求
//
// 
//优化思路:
// 
//假设两条从0到3的路径
//0 -> 1 -> 2 -> 3  18
//0 -> 2 -> 1 -> 3  20
//那么以0 -> 1 -> 2 -> 3为前面部分的方案一定是优于以0 -> 2 -> 1 -> 3为前面部分的方案的,这样就可以实现剪枝,从而降低时间复杂度
//
// 
//状态表示:
// 
//f[state][j],state表示哪些点被用过(被用过点的集合),j表示目前路径停在哪一个点上
//
//状态转移:
//
//state_k表示在state中去掉j的集合并且以k结尾的集合,weight[k][j]表示从k到j的边的权重
//遍历k
//f[state][j]=min{ f[state_k][k]+weight[k][j] };
//
//
//如何用state表示一个集合呢?
//
//状态压缩经典做法,二进制数表示状态
//一共有20位,就用一个20位的二进制数表示所有可能的集合
//假设0,1,4已经被用过了,那么集合state=10011
//
//
//算法时间复杂度分析:
//
//状态表示的state要2^20,j要20
//状态计算方程遍历k也要20
//所以总的时间复杂度为2^20*20*20约等于4*10^8,时间限制是5s,符合要求
//
//
//代码实现:
#include<iostream>
#include<algorithm>//min函数头文件
#include<cstring>//memset函数头文件
using namespace std;
const int N = 20, M = 1 << 20;
int f[M][N], weight[N][N];
int n;
int main()
{
    cin >> n;
    //输入带权无向图的权重
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> weight[i][j];
        }
    }
    //由于本题求的是最短路径长度,所以把f数组初始化为无穷大
    memset(f, 0x3f, sizeof f);
    //从0开始,0已经被用过,且现在停在0,所以state=1,j=0,此时还没有走过任何一条边所以初始化为0
    f[1][0] = 0;
    //动态规划,启动!
    //状态计算
    for (int i = 0; i < 1 << n; i++)//state
    {
        for (int j = 0; j < n; j++)//j
        {
            //遍历所有的状态
            //j的含义是当前路径停在j那么state就必须包含j
            if (i >> j & 1)//i>>j&1用于判断第j位是否为1,第j位是1这个状态才合法
            {
                for (int k = 0; k < n; k++)
                {
                    //去掉j,用同样的方法判断去掉j之后并且路径停在k的状态是否合法
                    if (i - (1 << j) >> k & 1)//去掉j之后第k位是1则是状态合法
                    {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }
    //答案就是0到n-1一共n个点都被用过,并且停在n-1的最短路径
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}