Autobus
Problem
Ci sono autobus tra alcuni villaggi della regione di Vasyuki. Poiché il traffico passeggeri qui non è molto elevato, gli autobus passano solo poche volte al giorno.
Maria Ivanovna deve spostarsi dal villaggio d al villaggio v il più velocemente possibile (è considerata nel villaggio d al tempo 0).
Input
Inserisci prima il numero N – numero totale di villaggi (1 <= N <= 100), poi i numeri del villaggio d e v, seguito dal numero di corse R (0 <= R <= 10000). Di seguito sono riportate le descrizioni dei percorsi degli autobus. Ogni volo è dato dal numero del villaggio di partenza, dall'orario di partenza, dal villaggio di destinazione e dall'orario di arrivo (tutti gli orari sono numeri interi da 0 a 10000). Se all'ora t un passeggero arriva in un villaggio, può lasciarlo in qualsiasi momento a partire da t.
Uscita
Stampa il tempo minimo in cui Maria Ivanovna può essere nel villaggio v. Se non può andare da d a v utilizzando i percorsi di autobus indicati, stampa -1.
Esempi
| # |
Input |
Uscita |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |