Module: Floyd-Algorithmus

Es wurde ein orientiertes gewichtetes Diagramm angegeben. Durch seine Adjazenzmatrix muss für jedes Scheitelpunktpaar bestimmt werden, ob der kürzeste Weg zwischen ihnen existiert oder nicht.

 

Kommentar: Der kürzeste Weg kann aus zwei Gründen nicht existieren:

Die erste Zeile der Eingabedatei enthält eine einzige Zahl: N (1 <=N <=100) — die Anzahl der Eckpunkte des Graphen. In den folgenden N Zeilen mit N Zahlen entspricht die Adjazenzmatrix des Graphen (die j. Zahl in der i. Zeile entspricht dem Gewicht der Kante von Scheitelpunkt i nach Scheitelpunkt j): Die Zahl 0 gibt an, dass keine Kante vorhanden ist, und jede andere Zahl hat eine Kante mit entsprechendem Gewicht. Alle Zahlen im Modul überschreiten 100 nicht.

 

Geben Sie N Zeilen mit N Zahlen aus. Die Zahl muss 0 sein, wenn der Pfad nicht existiert, 1, wenn der kürzeste Pfad existiert, und 2, wenn die Pfade existieren, aber es gibt Pfade, die beliebig klein sind.

Beispiele

№	Eingabe	Ausgabe
1	5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 0 -1 0 0 0 -1 0	1 1 1 0 0  1 1 1 0 0  1 1 1 0 0  0 0 0 2 2  0 0 0 2 2