Module: L'algoritmo di Floyd

Ti viene fornito un grafico ponderato diretto. Usando la sua matrice di adiacenza, devi determinare per ogni coppia di vertici se c'è o meno un percorso più breve tra di loro.

 

Commento: il percorso più breve potrebbe non esistere per due motivi:

La prima riga del file di input contiene un solo numero: N (1 <=N <=100) — il numero di vertici del grafo. Le successive N righe contengono N numeri ciascuna — matrice di adiacenza del grafico (il j-esimo numero nella i-esima riga corrisponde al peso dello spigolo dal vertice i al vertice j): il numero 0 significa nessun spigolo, e qualsiasi altro numero — la presenza di un bordo del peso corrispondente. Tutti i numeri modulo non superano 100.

 

Stampa N righe di N numeri. Il numero j-esimo nella riga i-esima deve corrispondere al percorso più breve dal vertice i al vertice j. Il numero dovrebbe essere 0 se non c'è percorso, 1 se c'è un percorso più breve e 2 se ci sono percorsi ma ci sono percorsi di peso arbitrariamente piccolo.

Esempi

#	Input	Uscita
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