Problem
Dado un gráfico dirigido que puede tener múltiples aristas y bucles. Cada borde tiene un peso expresado como un número entero (posiblemente negativo). Se garantiza que no hay ciclos de peso negativos.
Debe calcular las longitudes de los caminos más cortos desde el vértice número 1 hasta todos los demás vértices.
Entrada
El programa primero recibe el número N (1 <= N <= 100) – el número de vértices del gráfico y el número M (0 <= M <= 10000) – número de costillas. Las siguientes líneas contienen M triples de números que describen los bordes: el comienzo del borde, el final del borde y el peso (el peso es un número entero de -100 a 100).
Salida
El programa debe generar N números – distancias del vértice número 1 a todos los vértices del gráfico. Si no hay ruta al vértice correspondiente, imprima el número 30000 en lugar de la longitud de la ruta.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |