Ford Bellman
Problem
Dado um grafo direcionado que pode ter múltiplas arestas e loops. Cada aresta tem um peso expresso como um número inteiro (possivelmente negativo). É garantido que não há ciclos de peso negativo.
Você precisa calcular os comprimentos dos caminhos mais curtos do vértice número 1 para todos os outros vértices.
Entrada
O programa primeiro recebe o número N (1 <= N <= 100) – o número de vértices do gráfico e o número M (0 <= M <= 10000) – número de costelas. As linhas a seguir contêm M triplos de números descrevendo as arestas: o início da aresta, o fim da aresta e o peso (o peso – é um número inteiro de -100 a 100).
Saída
O programa deve gerar N números – distâncias do vértice número 1 a todos os vértices do grafo. Se não houver caminho para o vértice correspondente, imprima o número 30000 em vez do comprimento do caminho.
Exemplos
| # |
Entrada |
Saída |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |