Problem
Scrivi un programma che trovi le distanze in un grafo pesato non orientato con lunghezze degli archi non negative, da un dato vertice a ogni altro vertice. Il programma dovrebbe essere veloce per grandi grafici sparsi.
Input
La prima riga dell'input contiene il numero NUM — il numero di diverse esecuzioni dell'algoritmo di Dijkstra (su diversi grafici). Questo è seguito da NUM blocchi, ognuno dei quali ha la seguente struttura.
La prima riga del blocco contiene due numeri N e M separati da uno spazio — il numero di vertici e il numero di spigoli del grafo. Questo è seguito da M righe, ciascuna contenente tre numeri interi separati da spazi. I primi due, che vanno da 0 a N–1 ciascuno, denotano le estremità del bordo corrispondente, il terzo — compreso tra 0 e 20000 e denota la lunghezza di questo bordo. Inoltre, nell'ultima riga del blocco, un singolo numero da 0 a N–1 — picco, la distanza da cui devi cercare.
Il numero di grafici diversi in un test NUM non supera 5. Il numero di vertici non supera 60000, spigoli — 200000.
Impressum
Stampa sullo standard output (schermo) NUM righe, ciascuna contenente Ni numeri separati da spazi — la distanza dal vertice iniziale specificato del grafo non orientato pesato al suo 0°, 1°, 2°, ecc. vertici (è consentito uno spazio extra dopo l'ultimo numero). Se qualche vertice non è raggiungibile da quello iniziale specificato, stampa il numero 2009000999 al posto della distanza (è garantito che tutte le distanze reali sono inferiori).
Esempi
| # |
Input |
Uscita |
| 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 |