← 返回题目列表

Codeforces · 656/E

E. 失控

中文机器翻译题面 查看原题

给你一个完整的无向图。对于每对顶点,都会给出连接它们的边的长度。找到图中每对顶点之间的最短路径,并返回其中最长路径的长度。

输入

输入的第一行包含单个整数 N (3 ≤ N ≤ 10)。

以下 N 行每行包含 N 个空格分隔的整数。第 i 行中的第 j 个整数 aij 是连接顶点 i 和 j 的边的长度。 aij = aji, aii = 0, 1 ≤ aij ≤ 100(i ≠ j)。

输出

输出图中任意一对顶点之间的最短路径的最大长度。

示例

输入 #1

3
0 1 1
1 0 4
1 4 0

输出 #1

2

输入 #2

4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0

输出 #2

5

注意

您的关键字不足,因此无法使用其中一些关键字: