1394: Internet消息发布
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：75
解决：19
题目描述
设Internet上有N个站点，通常从一个站点发送消息给其他N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较长时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以 发布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应该会缩短消息传遍N个站点的时间。
请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从第一个站点开始发布消息传遍N个站点的最短时间。
请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从第一个站点开始发布消息传遍N个站点的最短时间。
输入
由文件 internet.in 输入数据，文件的第一行是 Internet 上的站点数 N（1<=N<=100），第二行起是邻接矩阵严格的下三角部分，各行是整数或字符 X。A(I, J)表示从 I 站点发送消息给 J 站点所需要的时间。假设网络是无方向的，故 A(I, J)＝A(J, I)，当 A(I, J)＝-1 时，表示从站点 I 不能直接向站点 J 发送消息；
A(I,I)＝0 表示没有必要自己给自己送消息（1<=I<=N），严格的下三角阵表示如下：
A(2, 1)
A(3, 1), A(3, 2)
A(4, 1), A(4, 2), A(4, 3)
┇
A(N, 1), A(N, 2)……A(N, N-1)
输出
输出只有一行，它是一个非负整数，若为 0 表示无解，非 0 表示合符题意的最小整数。
样例输入 复制
5
50
30 5
100 20 50
10 -1 -1 10
样例输出 复制
35