1-k BFS
Problem
Ti viene fornito un grafico ponderato diretto. Devi trovare la distanza dall'alto 1 a tutti gli altri, utilizzando l'algoritmo 1 - k BFS.
Input
La prima riga contiene 2 numeri interi n e m, rispettivamente il numero di vertici e archi nel grafico. Le seguenti righe m contengono ciascuna 3 numeri a e b - i vertici che il bordo connette e c - il peso di questo spigolo (a, b, c >= 0).
Uscita
È necessario emettere il numero n-1 separato da uno spazio - le distanze dall'alto 1 a tutti gli altri, se non c'è un percorso possibile da 1 a i< /code> vertice, allora devi generare Impossibile.
Esempi
| # |
Input |
Uscita |
| 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 Impossibile Impossibile Impossibile
|