Problem
Écrivez un programme qui trouvera les distances dans un graphe pondéré non orienté avec des longueurs d'arête non négatives, d'un sommet donné à tous les autres sommets. Le programme doit être rapide pour les grands graphes creux.
Entrée
La première ligne de l'entrée contient le nombre NUM — le nombre d'exécutions différentes de l'algorithme de Dijkstra (sur différents graphes). Ceci est suivi de NUM blocs, chacun ayant la structure suivante.
La première ligne du bloc contient deux nombres N et M séparés par un espace — le nombre de sommets et le nombre d'arêtes du graphe. Elle est suivie de M lignes, chacune contenant trois nombres entiers séparés par des espaces. Les deux premiers d'entre eux, allant de 0 à N–1 chacun, désignent les extrémités de l'arête correspondante, le troisième — allant de 0 à 20000 et désigne la longueur de cette arête. De plus, dans la dernière ligne du bloc, un seul chiffre de 0 à N–1 — pic, la distance à partir de laquelle vous devez rechercher.
Le nombre de graphiques différents dans un test NUM ne dépasse pas 5. Le nombre de sommets ne dépasse pas 60000, les arêtes — 200000.
Mentions légales
Imprimer sur la sortie standard (écran) NUM lignes, chacune contenant Ni nombres séparés par des espaces — la distance entre le sommet de départ spécifié du graphe non orienté pondéré et ses 0e, 1er, 2e, etc. sommets (un espace supplémentaire est autorisé après le dernier chiffre). Si un sommet est inaccessible à partir du premier spécifié, imprimez le nombre 2009000999 au lieu de la distance (il est garanti que toutes les distances réelles sont inférieures).
Exemples
| # |
Entrée |
Sortie |
| 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 |