Problem
Dado un gráfico dirigido a cuyos bordes se les asignan pesos no negativos (longitudes). Necesitamos encontrar dos vértices, el camino más corto entre los que tiene la mayor longitud.
Entrada
La primera línea contiene el número de vértices N ≤50. Luego viene la matriz de adyacencia del gráfico, es decir, N filas, cada una de las cuales contiene N números. El j-ésimo número en la i-ésima fila de la matriz de adyacencia especifica la longitud del borde que va desde el i-ésimo vértice hasta el j-ésimo. Las longitudes pueden tomar cualquier valor de 0 a 1000000. Se garantiza que haya ceros en la diagonal principal de la matriz.
Salida
Imprimir un solo número – la longitud de la ruta deseada.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|