ônibus
Problem
Existem ônibus entre algumas aldeias na região de Vasyuki. Como o tráfego de passageiros aqui não é muito grande, os ônibus circulam apenas algumas vezes ao dia.
Maria Ivanovna precisa ir da aldeia d para a aldeia v o mais rápido possível (considera-se que ela está na aldeia d no tempo 0).
Entrada
Primeiro digite o número N – número total de aldeias (1 <= N <= 100), em seguida, os números da aldeia d e v, seguido pelo número de viagens de ônibus R (0 <= R <= 10000). A seguir estão as descrições das rotas de ônibus. Cada voo é dado pelo número da aldeia de partida, hora de partida, aldeia de destino e hora de chegada (todos os tempos – são números inteiros de 0 a 10000). Se no momento t um passageiro chega a alguma aldeia, ele pode deixá-la a qualquer momento a partir de t.
Saída
Imprima o tempo mínimo em que Maria Ivanovna pode estar na aldeia v. Se ela não puder ir de d a v usando as rotas de ônibus fornecidas, imprima -1.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |