Ford Bellmann
Problem
Dato un grafico orientato che può avere più spigoli e loop. Ogni spigolo ha un peso espresso come numero intero (possibilmente negativo). È garantito che non ci sono cicli di peso negativi.
Devi calcolare le lunghezze dei percorsi più brevi dal vertice numero 1 a tutti gli altri vertici.
Input
Il programma riceve prima il numero N (1 <= N <= 100) – il numero di vertici del grafico e il numero M (0 <= M <= 10000) – numero di costole. Le righe seguenti contengono M triple di numeri che descrivono i bordi: l'inizio del bordo, la fine del bordo e il peso (il peso – è un numero intero compreso tra -100 e 100).
Uscita
Il programma dovrebbe produrre N numeri – distanze dal vertice numero 1 a tutti i vertici del grafico. Se non esiste un percorso per il vertice corrispondente, stampa il numero 30000 invece della lunghezza del percorso.
Esempi
| # |
Input |
Uscita |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |