【Highways】

题目描述

Wisekingdom 有 N 座城市,为了使 wisekingdom 的交通更加便利,国王决定修建高速公路,使得每两个城市之间都有高速公路相通。现在国王想知道的并不是修建的高速路的最小长度和。他感兴趣的是所建高速公路中最长的一条的长度,他希望这个最长长度尽量小。

输入格式

第一行:一个正整数 N ,  N<=500;
接下来 N 行,每行 N 个数。第 i 行第 j 个数表示 i,j 城市之间需要修建的高速路的长度(长度<=50000)。输入数据保证关于主对角线对称。

输出格式

仅一行:即所建公路的最小最大长度。

样例数据 1

输入

3
0 990 692
990 0 179
692 179 0

输出

692

备注

【数据说明】
40% 的数据:N<=50;
100% 的数据:N<=500。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*