#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; //#include "atcoder/all" // using namespace atcoder; //#pragma GCC optimize(3) //#pragma GCC optimize("Ofast") #define endl "\n" #define int long long #define double long double #define pii pair<int, int> #define p1(x) (x).first #define p2(x) (x).second #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) #define i128 __int128_t int n; int G[20][20]; bool p[20][20]; int g[1<<17][11][11]; int f[1<<17]; inline int ppc(int x){ return __builtin_popcount(x); } inline void chkmn(int &x,int y){ x=min(x,y); } inline int BF(){ int res=0; int N=1<<n; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(G[i][j]!=1e13){ if(G[i][j]<G[j][i]) G[j][i]-=G[i][j],res+=G[i][j],G[i][j]=0; else G[i][j]-=G[j][i],res+=G[j][i],G[j][i]=0; } memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g)); f[1]=0; for(int S=0;S<N;S++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i!=j&&(S&(1<<i))&&(S&(1<<j))) chkmn(g[S][i][j],f[S]); for(int k=0;k<n;k++){ chkmn(g[S|(1<<k)][k][j],g[S][i][j]+G[i][k]); if(S&(1<<i)&&i!=j&&i!=k&&j!=k) chkmn(g[S|(1<<j)|(1<<k)][k][i],f[S]+G[i][j]+G[j][k]); } } chkmn(f[S],g[S][i][i]); } } if(f[N-1]>=1e18)return -1; else return res+f[N-1]; } inline void slv(){ cin>>n; int ct=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ cin>>G[i][j],ct+=p[i][j]=G[i][j]!=-1; if(!p[i][j])G[i][j]=1e18; } cout<<BF()<<endl; } inline void MT(){ int t; cin>>t; while(t--)slv(); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // MT(); slv(); cout.flush(); return 0; } /* */