Problem
Schreiben Sie ein Programm, das die Abstände in einem nicht ausgerichteten gewichteten Graphen mit nicht negativen Kantenlängen vom angegebenen Scheitelpunkt bis zu allen anderen abdeckt. Das Programm sollte für große, spärliche Graphen schnell funktionieren.
Eingabe
In der ersten Zeile der Eingabe wird die Anzahl NUM angegeben, die Anzahl der verschiedenen Ausführungen des Dijkstra-Algorithmus (in verschiedenen Graphen). Es folgen die NUM-Blöcke, von denen jeder die folgende Struktur hat.
Die erste Zeile des Blocks enthält zwei Zahlen N und M, getrennt durch ein Leerzeichen; Anzahl der Scheitelpunkte und Anzahl der Kanten des Graphen. Gefolgt von M Strings, die jeweils drei durch Leerzeichen getrennte ganze Zahlen enthalten. Die ersten beiden sind im Bereich von 0 bisN–1 jeweils die Enden der entsprechenden Kante, die dritte im Bereich von 0 bis 20.000 und bezeichnet die Länge dieser Kante. Als nächstes wird in der letzten Zeile des Blocks eine einzige Zahl zwischen 0 und N–1 — der Scheitelpunkt, von dem aus nach Abstand gesucht werden soll.
Die Anzahl der verschiedenen Graphen in einem NUM-Test überschreitet nicht 5. Die Anzahl der Scheitelpunkte überschreitet nicht 60.000, die Kanten 200.000.
Ausgabe
Geben Sie in der Standardausgabe (Anzeige) NUM Zeilen aus, die jeweils durch Ni durch Leerzeichen getrennte Zahlen aus dem Abstand vom angegebenen Startpunkt des gewichteten, nicht orientierten Graphen zu seinem 0., 1., 2. und t. d. Scheitelpunkten (ein zusätzliches Leerzeichen nach der letzten Zahl ist erlaubt). Wenn ein Eckpunkt von dem angegebenen Anfangswert nicht erreichbar ist, geben Sie anstelle der Entfernung die Zahl 2009000999 aus (es wird garantiert, dass alle tatsächlichen Abstände kleiner sind).
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |