1-k BFS
Problem
Você recebe um gráfico ponderado direcionado. Você precisa encontrar a distância do 1 superior para todos os outros, usando o algoritmo 1 - k BFS.
Entrada
A primeira linha contém 2 inteiros n e m, o número de vértices e arestas no gráfico, respectivamente. As seguintes linhas m contêm 3 números cada a e b - os vértices que a aresta conecta e c - o peso desta aresta (a, b, c >= 0).
Saída
É necessário fornecer o número n-1 separado por um espaço - as distâncias do 1 superior para todos os outros, se não houver caminho possível de 1 para o vértice i< /code>, então você precisa gerar Impossível.
Exemplos
| # |
Entrada |
Saída |
| 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 Impossível Impossível Impossível
|