Rivières asséchées – Regional event 2019

Level 6

Énoncé

Delphine veut aider un troupeau de buffles pourchassé par des hyènes à s’enfuir sur un plateau où ils seront en sécurité. Il faudra parfois attendre qu’une rivière soit asséchée pour que les buffles puissent la traverser.

Delphine connait la liste des zones de la région, et sait prédire quand une rivière séparant deux zones sera asséchée. Elle sait que la rivière $i$ est asséchée pendant un jour tous les $p_i$ jours et qu'il faudra attendre $d_i$ jours à partir d'aujourd'hui avant qu'elle ne soit asséchée pour la première fois. Par exemple si $d_i = 1$ et $p_i = 3$, la rivière $i$ ne pourra pas être traversée le premier jour, mais seulement les 2ᵉ, 5ᵉ, 8ᵉ, 11ᵉ etc... jours.

Pour ne pas se faire rattraper par les hyènes, il est nécessaire que le troupeau soit en permanence en train de changer de zone, les zones de la savanes sont telles qu’il faut toujours exactement un jour pour se déplacer de l’une à l’autre. Donnez, si c’est possible, le temps minimal qu’il faudra à Delphine pour mettre le troupeau en sécurité.

Entrée

Sur la première ligne, l'entier $N$, le nombre de zones partitionnant la savane La zone d’indice $1$ est la position de départ du troupeau, la zone d’indice $N$ représente le plateau où le troupeau sera en sécurité.

Sur la seconde ligne, l'entier $M$, le nombre de rivières.

Sur les $M$ lignes suivantes: 4 entiers $x_i$, $y_i$, $p_i$, $d_i$ représentants la rivière $i$

  • La rivière sépare les zones $x_i$ et $y_i$
  • La rivière est asséchée après $d_i$ déplacements du troupeau, puis tous les $p_i$ déplacements

Sortie

S’il n’est pas possible de mettre le troupeau en sécurité, retournez IMPOSSIBLE.

Sinon, affichez le temps minimal, en jours, qu’il faut pour mettre le troupeau en sécurité.

Contraintes

  • $N \leq 2 000$
  • $M \leq 20 000$
  • $1 \leq x, y \leq N$
  • Le produit des périodes distinctes des rivières est plus petit que $1000$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4
4
1 2 2 0
1 3 2 0
2 3 2 1
3 4 2 0
Sample output
3
Note

Il est possible d'aller de la zone 1 à la zone 4 en 3 jours. Si on voulait passer par la zone 3 dès le jour 1, la rivière séparant les zones 3 et 4 bloquerait le passage vers la zone d'arrivée.

Sample input
4
4
1 2 3 0
2 3 3 1
3 1 3 2
3 4 2 1
Sample output
6
Note

Il n'y a qu'une seule zone accessible par jour, jusqu'au jour 5, ce qui contraint les déplacements du troupeau.

Submit your solution

You have to register or log in to be able to submit your solution.