Der längste Weg
Problem
Es ist ein orientierter Graph gegeben, dessen Kanten einige nicht negative Gewichte (Längen) zugeordnet sind. Es ist notwendig, zwei Eckpunkte zu finden, die den kürzesten Weg zwischen denen die längste Länge haben.
Eingabe
Die erste Zeile enthält die Anzahl der Scheitelpunkte von N ≤50. Als nächstes kommt die Adjazenzmatrix des Graphen, dh N Zeilen, von denen jede N Zahlen enthält. die j-ten Zahl in der i-ten Zeile der Adjazenzmatrix gibt die Länge der Kante an, die vom i-ten Scheitelpunkt zum j-ten führt. Die Längen können beliebig zwischen 0 und 1000000 liegen. Es ist garantiert, dass Nullen auf der Hauptdiagonale der Matrix stehen.
Ausgabe
Geben Sie eine Zahl aus, – die Länge des gewünschten Pfads.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|