dd爱探险

题号：NC221821
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

星际中有 $n$ 个空间站，任意两个空间站间可以相互跳跃，由空间站 $x$ 跳跃到空间站 $y$ 所需要的代价为 $P[x][y]$ ,注意不保证 $p[x][y]=p[y][x]$ ， $dd$ 可以任意选择出发的空间站，并通过恰好 $n-1$ 次跳跃把所有空间站跳完，并且 $dd$ 必须选择 $2$ 次跳跃，其中一次跳跃中进行重力加速，另一次跳跃中进行反重力加速，重力加速会导致当前跳跃代价变为 $0$ ，反重力加速会导致当前跳跃代价翻倍(乘 $2$ )，问跳完所有空间站所需要最小代价

输入描述:

第一行一个数n(3≤n≤16)
接下来n行每行n个数，第x行第y个数表示p[x][y](0≤p[x][y]≤100000)

输出描述:

一个数,表示最小代价

示例1

输入

复制

输出

复制

说明

1->2重力加速
2->3反重力加速
代价0+1*2=2