Dijkstra: recuperação de caminho
Problem
Você recebe um gráfico ponderado direcionado. Encontre o caminho mais curto de um dado vértice para outro.
Entrada
A primeira linha contém três números: N, S e F (1≤N≤100, 1≤S, F≤N), onde N – número de vértices do grafo, S – vértice inicial e F – final. Nas próximas N linhas, insira N números cada, não excedendo 100, – matriz de adjacência de gráfico, onde -1 significa nenhuma aresta entre os vértices e qualquer número não negativo – a presença de uma aresta de determinado peso. Os zeros são escritos na diagonal principal da matriz.
Saída
É necessário exibir sequencialmente todos os vértices de um (qualquer) dos caminhos mais curtos, ou um número -1 se não houver caminho entre os vértices especificados.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |