O caminho mais longo
Problem
Dado um grafo direcionado cujas arestas recebem alguns pesos (comprimentos) não negativos. Precisamos encontrar dois vértices, o caminho mais curto entre o qual tem o maior comprimento.
Entrada
A primeira linha contém o número de vértices N ≤50. A seguir vem a matriz de adjacência do grafo, ou seja, N linhas, cada uma contendo N números. O j-ésimo número na i-ésima linha da matriz de adjacência especifica o comprimento da aresta que vai do i-ésimo vértice ao j-ésimo. Comprimentos podem assumir qualquer valor de 0 a 1.000.000. É garantido que haja zeros na diagonal principal da matriz.
Saída
Imprimir um único número – o comprimento do caminho desejado.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|