Rivières asséchées – Épreuve régionale 2019

Niveau 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$

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
4
1 2 2 0
1 3 2 0
2 3 2 1
3 4 2 0
Exemple de sortie
3
Commentaire

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.

Exemple d'entrée
4
4
1 2 3 0
2 3 3 1
3 1 3 2
3 4 2 1
Exemple de sortie
6
Commentaire

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