Prologin
2026
Énoncé¶
Joseph pense avoir trouvé un endroit où se cachent les robots indépendantistes ! En entrant dans l'entrepôt, il se rend compte que les robots sont dans une pièce à l'autre bout. Afin de les rejoindre, il doit emprunter un dédale de portes et couloirs.
L'entrepôt est constitué de $P$ pièces et de $N$ couloirs les reliant. Au milieu de chaque couloir peut se trouver une porte d'une couleur entre $1$ et $M$.
Des règles strictes de sécurité sont appliquées dans cet entrepôt : Joseph ne peut emprunter plus de $S$ fois d'affilée une porte de la même couleur.
Étant donné un plan de l'entrepôt, déterminez le nombre minimum de portes que Joseph devra franchir pour atteindre la pièce de sortie où se trouvent les robots.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, le nombre de couloirs de l'entrepôt.
- Sur la ligne suivante, un entier : P, le nombre de pièces de l'entrepôt.
- Sur la ligne suivante, un entier : M, le nombre de couleurs différentes pouvant être appliquées aux portes.
- Sur la ligne suivante, un entier : S, le nombre de portes de la même couleur pouvant être franchies sans interruption.
- Sur la ligne suivante, un entier : X, la pièce de départ.
- Sur la ligne suivante, un entier : Y, la pièce d'arrivée.
- Sur les lignes suivantes, une liste de N éléments : entrepot, la liste
de tous les couloirs de l'entrepôt.
- Une ligne par élément de la liste : séparés par des espaces, un entier A (la première pièce), un entier B (la seconde pièce), et un entier C (la couleur de la porte du couloir, ou 0 s'il n'y a pas de porte).
Sortie¶
Afficher le nombre minimum de portes franchies afin d'atteindre la pièce
d'arrivée. Si cela n'est pas possible, afficher -1.
Contraintes¶
- $1 \le N \le 2\,750$
- $2 \le P \le 1\,750$
- $2 \le M \le N$
- $1 \le S \le N$
- $1 \le A, B, X, Y \le P$
- $0 \le C \le M$
Contraintes de performance¶
- $1 \le N \le 8\,250$
- $2 \le P \le 7\,000$
