题目描述

快递员要将 n 份快餐送到 n 个不同的地方，编号为 1~n，快递员所在的公司编号为 0，现在他从公司出发，要到达这 n 个地方至少一次，送完后再回到公司，请问最短时间是多少。现在已知任意两个城市的直接通路的时间。

输入格式

第一行一个正整数 n。
接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过 10000 的正整数。矩阵
的i行j列表示第 i - 1 号城市和 j - 1 号城市之间直接通路的时间。当然城市 a 到城市 b 的直接通
路时间和城市 b 到城市 a 的直接通路时间不一定相同，也就是说道路都是单向的。

输出格式

仅有一个正整数表示最少花费的时间。

样例输入

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0

样例输出

8

数据范围

对于 50%的数据1 <= n <= 10
对于 100%的数据1 <= n <= 15

限制

1s

来源

CWOI新高二专题测试四