1-k BFS
Problem
On vous donne un graphique pondéré orienté. Vous devez trouver la distance entre le sommet 1 et tous les autres, en utilisant l'algorithme 1 - k BFS.
Entrée
La première ligne contient 2 entiers n et m, le nombre de sommets et d'arêtes dans le graphe, respectivement. Les lignes m suivantes contiennent 3 nombres chacun a et b - les sommets que l'arête relie et c - le poids de cette arête (a, b, c >= 0).
Sortie
Il est nécessaire de sortir le numéro n-1 séparé par un espace - les distances du haut 1 à tous les autres, s'il n'y a pas de chemin possible depuis 1 au sommet i, alors vous devez sortir Impossible.
Exemples
| # |
Entrée |
Sortie |
| 1 |
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
1 4 3 6 4 Impossible Impossible Impossible