Ford Bellman
Problem
Étant donné un graphe orienté qui peut avoir plusieurs arêtes et boucles. Chaque arête a un poids exprimé sous forme d'entier (éventuellement négatif). Il est garanti qu'il n'y a pas de cycles de poids négatifs.
Vous devez calculer les longueurs des chemins les plus courts du sommet numéro 1 à tous les autres sommets.
Entrée
Le programme reçoit d'abord le nombre N (1 <= N <= 100) – le nombre de sommets du graphe et le nombre M (0 <= M <= 10000) – nombre de côtes. Les lignes suivantes contiennent M triplets de nombres décrivant les arêtes : le début de l'arête, la fin de l'arête et le poids (le poids – est un entier compris entre -100 et 100).
Sortie
Le programme devrait afficher N nombres – distances du sommet numéro 1 à tous les sommets du graphe. S'il n'y a pas de chemin vers le sommet correspondant, imprimez le nombre 30000 au lieu de la longueur du chemin.
Exemples
| # |
Entrée |
Sortie |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
0 10 20 30000 30000 30000 |