Module: Floyd-Algorithmus


Problem

4 /10


Der kürzeste Weg

Theory Click to read/hide

Wenn es Zyklen von negativem Gewicht in der Box, der formale Algorithmus Floyd-Worschella gilt nicht für eine solche Zeile.

Tatsächlich funktioniert der Algorithmus für diejenigen Spitzen i und j, zwischen denen das negative Gewicht nicht erreicht werden kann.

Für die gleichen Paare von Peaks, für die keine Antwort besteht (wegen des negativen Zyklus zwischen ihnen), wird der Floyd-Algorithmus eine Anzahl (möglicherweise negativ, aber nicht notwendig) finden. Allerdings kann der Floyd-Algorithmus verbessert werden, so dass er solche Peaks für sie sorgfältig verarbeiten und entfernen kann, beispielsweise- Ja.♪

Beispielsweise kann Folgendes geschehen:Kriterium"Nein." Okay, lassen Sie uns einen regelmäßigen Floyd-Algorithmus auf dieser Zählung haben. Dann gibt es keinen kürzesten Weg zwischen den Oberseiten von i und j zu der Zeit und nur, wenn es einen solchen Peak t, erzielbar von i und erzielbar j, für den es erfüllt ist- Ja.♪

Darüber hinaus sollte mit dem Floyd-Algorithmus für negative Zyklenzahlen daran erinnert werden, dass die im Laufe der Operation auftretenden Abstände sehr weit bis minus, exponentiell mit jeder Phase gehen können. Maßnahmen sollten daher gegen die Anzahl der überfüllten Maßnahmen ergriffen werden, die alle Abstände auf jeden Wert begrenzen (z.B.)- Ja.)

Eine seltene Lösung kann so beschrieben werden, dass
Nachdem Floyd-Worschellas Algorithmus für die vordere Reihe funktioniert, nehmen wir alle Spitzen.- Ja.Und für jedes dieser Paare überprüfen wir, ob die kürzeste Route von i zu j oder nicht. Wir nehmen den dritten Top-T dafür, und wenn es sich herausstellt, sie zu sein.- Ja.(d.h., es ist im negativen Gewichtszyklus) und es ist von und von i erzielbar j ist der Pfad- Ja.kann eine unendlich kleine Länge haben.

Problem

Es wird ein orientierter voller Graph gegeben, dessen Kanten Gewichte (Längen) zugeordnet sind. Gewichte können sowohl positiv als auch negativ und Null sein. Wir sind an den minimalen Längen aller möglichen Pfade zwischen allen Paaren verschiedener Eckpunkte dieses Graphen interessiert. Es wird notwendig sein herauszufinden, ob dieses Minimum existiert, und, falls vorhanden, es zu berechnen. (Es gibt kein Minimum, wenn ein Pfad mit negativer Länge in einem Diagramm gefunden werden kann, beliebig groß modular, der nach Unendlichkeit strebt).
 
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 -1000000 und 1000000 liegen. Es ist garantiert, dass Nullen auf der Hauptdiagonale der Matrix stehen.
 
Ausgabe
Geben Sie eine Zahl aus, – das gesuchte Minimum. Wenn es nicht existiert, geben Sie  -1 aus.
Beispiele
№ Eingabe Ausgabe
1
3
0 42 18468 
6335 0 26501 
19170 15725 0 
 42
2
3
0 -7 3
-2 0 10
2 215 0 
 -1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!