Module: Algorithme de Dijkstra

Il y a des bus entre certains villages de la région de Vasyuki. Comme le trafic de passagers ici n'est pas très important, les bus ne circulent que quelques fois par jour.

 

Maria Ivanovna doit se rendre du village d au village v le plus rapidement possible (elle est considérée comme étant dans le village d au temps 0).

 

Entrez d'abord le nombre N – nombre total de villages (1 <= N <= 100),  puis les numéros de village d et v,  suivi du nombre de trajets en bus R (0 <= R <= 10000). Voici les descriptions des lignes de bus. Chaque vol est donné par le numéro du village de départ, l'heure de départ, le village de destination et l'heure d'arrivée (tous les horaires sont des nombres entiers de 0 à 10000). Si à l'instant t un passager arrive dans un village, il peut le quitter à tout moment à partir de t.

 

Imprimez le temps minimum pendant lequel Maria Ivanovna peut être dans le village v. Si elle ne peut pas se rendre de d à v en utilisant les itinéraires de bus indiqués, écrivez -1.
Exemples

3

1 3

4

1 0 2 5

1 1 2 3

2 3 3 5

1 1 3 10

#	Entrée	Sortie
1	5