Problem
Escreva um programa que encontre as distâncias em um gráfico ponderado não direcionado com comprimentos de borda não negativos, de um determinado vértice a todos os outros vértices. O programa deve ser rápido para grandes gráficos esparsos.
Entrada
A primeira linha da entrada contém o número NUM — o número de execuções diferentes do algoritmo de Dijkstra (em gráficos diferentes). Isso é seguido por NUM blocos, cada um com a seguinte estrutura.
A primeira linha do bloco contém dois números N e M separados por um espaço — o número de vértices e o número de arestas do grafo. Isso é seguido por M linhas, cada uma contendo três números inteiros separados por espaços. Os dois primeiros, variando de 0 a N–1 cada, denotam as extremidades da aresta correspondente, o terceiro — variando de 0 a 20000 e denota o comprimento dessa aresta. Além disso, na última linha do bloco, um único número de 0 a N–1 — pico, a distância a partir da qual você precisa pesquisar.
O número de gráficos diferentes em um NUM de teste não excede 5. O número de vértices não excede 60000, arestas — 200000.
Impressão
Imprime na saída padrão (tela) NUM linhas, cada uma contendo Ni números separados por espaços — a distância do vértice inicial especificado do gráfico não direcionado ponderado até seu 0º, 1º, 2º, etc. vértices (um espaço extra é permitido após o último número). Se algum vértice for inacessível a partir do inicial especificado, imprima o número 2009000999 em vez da distância (é garantido que todas as distâncias reais são menores).
Exemplos
| # |
Entrada |
Saída |
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |