Лимит времени 1000/1000/1000/1000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem description
Given a connected weighted graph with N vertices. A diameter of graph is maximum of shortest distances between any 2 vertices. Find diameter of given graph.
Input
There is a single integer N on the first line (1 ≤ N ≤ 100). There are N integers on each of N next lines. Where (i, j) = -1 if cities i and j are not connected, and any nonnegative integer not bigger than 1000 which denotes distance between i and j.
Output
Write maximum of shortest distances between 2 vertices.
Example
| stdin |
stdout |
4
0 -1 1 2
-1 0 -1 5
1 -1 0 4
2 5 4 0 |
8 |
Для отправки решений необходимо выполнить вход.
|