Busse
Problem
Busse verkehren zwischen einigen Dörfern der Region Vasyuki. Da der Personenverkehr hier nicht sehr groß ist, fahren die Busse nur mehrmals am Tag.
Maria Iwanowna muss so schnell wie möglich vom Dorf d nach Dorf v gelangen (es wird angenommen, dass sie sich zum Zeitpunkt 0 im Dorf d befindet).
Eingabe
Zuerst wird die Zahl N – die Gesamtzahl der Dörfer (1 <= N <= 100) eingegeben, dann die Dorfnummern d und v,gefolgt von der Anzahl der Busverbindungen R (0 <= R <= 10000). Als nächstes kommen die Beschreibungen der Busfahrten. Jeder Flug wird durch die Nummer des Abfahrtsortes, die Abfahrtszeit, das Zieldorf und die Ankunftszeit angegeben (alle Zeiten, ganze Zahlen zwischen 0 und 10.000). Wenn ein Passagier zum Zeitpunkt t in ein Dorf kommt, kann er es jederzeit verlassen, beginnend mit t.
Ausgabe
Geben Sie die minimale Zeit an, in der Maria Ivanovna möglicherweise im Dorf v. sein kann. Wenn sie mit den angegebenen Busflügen nicht von d nach v gelangen kann, geben Sie -1 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |