La via più lunga
Problem
Dato un grafo orientato ai cui archi sono assegnati dei pesi (lunghezze) non negativi. Dobbiamo trovare due vertici, il percorso più breve tra i quali ha la lunghezza maggiore.
Input
La prima riga contiene il numero di vertici N ≤50. Poi viene la matrice di adiacenza del grafico, cioè N righe, ognuna delle quali contiene N numeri. Il numero j-esimo nella riga i-esima della matrice di adiacenza specifica la lunghezza del bordo che va dall'i-esimo vertice al j-esimo. Le lunghezze possono assumere qualsiasi valore compreso tra 0 e 1000000. È garantito che ci siano zeri sulla diagonale principale della matrice.
Uscita
Stampa un singolo numero – la lunghezza del percorso desiderato.
Esempi
| # |
Input |
Uscita |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|