The longest way
Problem
Given a directed graph whose edges are assigned some non-negative weights (lengths). We need to find two vertices, the shortest path between which has the greatest length.
Input
The first line contains the number of vertices N ≤50. Next comes the adjacency matrix of the graph, that is, N rows, each of which contains N numbers. The j-th number in the i-th row of the adjacency matrix specifies the length of the edge leading from the i-th vertex to the j-th one. Lengths can take any value from 0 to 1000000. It is guaranteed that there are zeros on the main diagonal of the matrix.
Output
Print a single number – the length of the desired path.
Examples
| # |
Input |
Output |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|