Problem
Se le proporciona un gráfico ponderado dirigido. Encuentra el camino más corto de un vértice dado a otro.
Entrada
La primera línea contiene tres números: N, S y F (1≤N≤100, 1≤S, F≤N), donde N – número de vértices del gráfico, S – vértice inicial y F – final. En las próximas N líneas, ingrese N números cada uno, sin exceder 100, – matriz de adyacencia gráfica, donde -1 significa que no hay borde entre los vértices, y cualquier número no negativo – la presencia de una arista de peso dado. Los ceros se escriben en la diagonal principal de la matriz.
Salida
Se requiere mostrar secuencialmente todos los vértices de uno (cualquiera) de los caminos más cortos, o un número -1 si no hay ningún camino entre los vértices especificados.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |