题目描述

BIT公司最近接收了一台新型超级计算机，这是一台配备$32$个处理器的Apollo Odyssey分布式共享内存机器，具有分层通信子系统。Valentine McKee的研究导师Jack Swigert要求她对这套新系统进行基准测试。

"由于Apollo采用分布式共享内存架构，内存访问和通信时间并不均匀，"Valentine向Swigert解释道，"共享相同内存子系统的处理器间通信较快，而不同子系统间的通信较慢。Apollo与我们实验室其他机器间的通信则更加迟缓。"

"Apollo移植的Message Passing Interface（MPI）运行情况如何？"Swigert询问道。

"不太理想，"Valentine回答，"目前要实现从单个处理器向其他$n-1$个处理器广播消息，他们只是简单地进行$n-1$次串行发送。这种方式严重限制了性能表现。"

"有什么改进方案吗？"

"当然，"Valentine微笑道，"当第一个处理器将消息发送给另一个处理器后，这两个处理器就能同时向其他两个主机发送消息。接着四个主机可以同时发送，依此类推。"

"啊，所以可以采用二叉树结构进行广播！"

"不完全是二叉树——我们的网络具有特殊特性需要利用。接口卡允许每个处理器同时向任意多个相连处理器发送消息。但由于通信链路成本差异，消息并非同时到达目标。我们需要综合考虑网络拓扑中各链路的通信成本，规划最优广播方案以最小化总耗时。"

输入格式

第一行输入处理器数量$n$（$1 \leq n \leq 100$）。

后续输入定义邻接矩阵$A$，其为$n \times n$的方阵。矩阵元素为整数或字符x：$A(i,j)$表示节点$i$到$j$的直接通信耗时，x表示不可达。

注意：

• 节点自通信耗时为$0$，即$A(i,i) = 0$（$1 \leq i \leq n$）
• 网络为无向图，故$A(i,j) = A(j,i)$
• 仅需输入矩阵的严格下三角部分

具体输入方式：

• 第二行：$A(2,1)$
• 第三行：$A(3,1)$ $A(3,2)$
• 依此类推...

输出格式

输出从第一个处理器向所有其他处理器广播消息所需的最小通信时间。

输入样例

5
50
30 5
100 20 50
10 x x 10

输出样例

35

题目来源

$1996$年北美中东部地区竞赛