#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define lll __int128_t
#define ulll __uint128_t
#define ld long double
#define lld __float128
#define fi first
#define se second
#define mp make_pair
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U>
bool chmax(T &x, U v) {return (v > x)? x=v,1 : 0;}
template<typename T, typename U>
bool chmin(T &x, U v) {return (v < x)? x=v,1 : 0;}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#define DEBUG
#ifdef DEBUG
#define _main "\e[36m"
#define _reset "\e[39m\n"
template<typename T>
inline void __print(T x) {cerr << x;}
template<typename T, typename U>
inline void __print(pair<T,U> x)
{
cerr << "("; __print(x.fi); cerr << ", "; __print(x.se); cerr << ")";
}
inline void _print() {}
template<typename T, typename... U>
inline void _print(T x, U... y)
{
__print(x);
if(sizeof...(y)) cerr << ", ";
_print(y...);
}
template<typename T>
inline void _print_arr(T x) {__print(x);}
template<typename T, typename... U>
inline void _print_arr(T x, int size, U... len)
{
cerr << "[";
bool has = sizeof...(len);
for(int i = 0; i < size; i++)
{
if(i) cerr << "," << (has? "\n" : " ");
_print_arr(x[i], len...);
}
cerr << "]";
}
#define _source source_location::current()
#define debug_pref(a) cerr << _main << _source.file_name() << ":" << _source.line() << ":" << _source.column() << " [" << a << "]";
#define debug(a...) {debug_pref(#a); cerr << " = ["; _print(a); cerr << "]" << _reset;}
#define debug_arr(a, sz...) {debug_pref(#a); cerr << " = "; _print_arr(a, sz); cerr << _reset;}
#endif
#ifndef DEBUG
#define debug(a...)
#define debug_arr(a, sz...)
#endif
/*
for root we have N^2 dp states
for second children we got (N/2)^2 * 2 and so on
total sum is N^2
we only gotta combine fast
we know how to do that in O(N^4) in a naive way
is there a better way?
dp[a][b] = min(dp1[a][c] + cost[c][d] + dp2[d][b])
min over sums is a convolution, but im not sure we can put cost here
we have to exploit tree structure
for a tree of size n, we have 2^(n-1) possible permutations
if we want 1 as the left node, we have 2^(n-2) permutations (one swap is forced)
if we want 2 its the same
now if we want 3 or 4, its 2^(n-3) (two swaps are forced)
for 5 ... 8 its 2^(n-4) (three swaps are forced) and the pattern repeats
note that doing swaps doesnt do anything inside the tree, you can reverse everything and get the same answer
its only used for the parent
lets try to calculate dp layer by layer?
sounds hard
lets think of a path in a graph, can we reduce this problem to that?
say for subtree v we have that path from a to b is minimum value with starting in a and ending in b
now we want to combine both
create graph where for every guy a we have two new nodes: sa, fa (start in a, finish in a)
st[v][a] = sa. add edge from sa to s[v*2][a]
from f[v*2][b] add edge to fb
do the same for the other node v*2+1
now connect fa from v*2 with sb from v*2+1
then do the opposite, fb to sa
now a path between sa and fd looks like this:
sa - s[v*2][a] - path inside v*2 - f[v*2][b] - fb - sc - s[v*2+1][c] - path inside v*2+1 - f[v*2+1][d] - fd
so we built a graph where minimum cost for start and end value is a shortes path
how many edges and nodes?
V(n) - num of nodes
E(n) - num of edges
V(n) = V(n/2)*2 + n*2
E(n) = E(n/2)*2 + (n/2)^2 * 2
V(1) = 1
E(1) = 0
V(n) = O(n log n)
E(n) = O(n^2)
doesnt work really, a few more nodes
each path must remember, whether its first or last
V(n) = V(n/2) * 4
V(n) = N^2
E(n) = E(n/2)*4 + (n/2)^2*2 = n^2/2
E(n) <= E(n/2)*4 + n^2
E(1) <= 1
E(2) <= 8
E(4) <= 48
E(N) = N^2 log N?
i think this can be optimised
dp[i][v] -> dp[i+1][u]
for i&1 == 0 (N/2 i's) one edge
for i&3 == 01 (N/4 i's) two edges
for i&7 == 011 (N/8 i's) four edges
N/2 + N/4*2 + N/8*4 .... = N log N edges
for each value v we get N^2 log N transitions among N^2 states
no dijkstra!
*/
const int MAXN = 2100;
ll dp[MAXN][MAXN];
int cost[MAXN][MAXN];
int main()
{
fast;
int n; cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> cost[i][j];
}
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
dp[i][j] = 1e18;
}
}
for(int v = 0; v < n; v++)
{
dp[0][v] = 0;
}
for(int i = 0; i < n-1; i++)
{
int cnt = 0, x = i+1;
while(x % 2 == 0)
{
cnt++;
x /= 2;
}
for(int v = 0; v < n; v++)
{
for(int xr = 0; xr < (1 << cnt); xr++)
{
int nv = v ^ xr ^ (1 << cnt);
chmin(dp[i+1][nv], dp[i][v] + cost[v][nv]);
}
}
}
ll ans = 1e18;
for(int v = 0; v < n; v++)
{
chmin(ans, dp[n-1][v]);
}
cout << ans;
}
/*
2
0 2
2 0
4
0 2 3 1
2 0 4 5
3 4 0 3
1 5 3 0
8
0 2 5 8 5 9 2 6
2 0 8 4 3 7 5 3
5 8 0 3 8 4 3 3
8 4 3 0 2 2 7 7
5 3 8 2 0 7 3 3
9 7 4 2 7 0 6 7
2 5 3 7 3 6 0 4
6 3 3 7 3 7 4 0
*/
