Module: algoritmo de Floyd

Você recebe um gráfico ponderado direcionado. Usando sua matriz de adjacência, você precisa determinar para cada par de vértices se existe um caminho mais curto entre eles ou não.

 

Comentário: O caminho mais curto pode não existir por dois motivos:

A primeira linha do arquivo de entrada contém um único número: N (1 <=N <=100) — o número de vértices do gráfico. As próximas N linhas contêm N números cada — matriz de adjacência do gráfico (o j-ésimo número na i-ésima linha corresponde ao peso da aresta do vértice i ao vértice j): o número 0 significa nenhuma aresta e qualquer outro número — a presença de uma borda do peso correspondente. Todos os números de módulo não excedem 100.

 

Imprime N linhas de N números. O j-ésimo número na i-ésima linha deve corresponder ao caminho mais curto do vértice i ao vértice j. O número deve ser 0 se não houver caminho, 1 se houver um caminho mais curto e 2 se houver caminhos, mas caminhos de peso arbitrariamente pequeno.

Exemplos

#	Entrada	Saída
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