Module: Floyd-Algorithmus

Es wurde ein nicht orientierter Gewichtungsgraph mit negativen Gewichtungen angegeben, und es ist notwendig, Informationen über den kürzesten Weg zwischen zwei Stützpunkten zu erhalten.

Eingabe
In der ersten Zeile wird die ganze Zahl n angegeben - die Anzahl der Scheitelpunkte im Diagramm. Als nächstes wird eine Adjazenzmatrix an den Eingang geliefert, wobei -1 bedeutet, dass keine Kante zwischen den Scheitelpunkten vorhanden ist. Nach der Matrix folgt die Zahl k - die Anzahl der Abfragen, die folgenden k Zeilen enthalten jeweils 2 Zahlen, a und b - die Eckpunkte in der Abfrage.

Ausgabe
Die Zeichenfolge muss k von Zahlen enthalten - der Abstand zwischen einem Zahlenpaar aus der Abfrage in der Reihenfolge ihrer Eingabe. Wenn Sie nicht vom Eckpunkt a zum Eckpunkt b gelangen können, sollten Sie Imp ausgeben.