Prologin
2024
Énoncé¶
La machine à voyager de nos chers amis peut présenter des pannes en cas de surchauffe. Pour éviter ce genre de pannes, il faudrait mettre en place un système de refroidissement.
La machine contient $N$ points pouvant être reliés par des tuyaux. Chaque tuyau refroidit le liquide y passant d'un certain nombre de degrés. Les tuyaux ne sont pas bidirectionnels.
Votre but est de savoir combien de tuyaux au minimum composent un chemin refroidissant d'au moins $K$ degrés le liquide. Ce chemin commence par le point $A$ et se termine au point $B$. Pour cela, vous disposerez du plan de la machine comprenant les points et les emplacements possibles des tuyaux.
Dans ce plan, s'il existe un emplacement de tuyau entre les points $U$ et $V$, alors vous pouvez construire autant de tuyaux entre ces points (possiblement aucun tuyau). Pour des raisons physiques, votre chemin ne peut pas emprunter plusieurs fois le même tuyau. Cependant, vous pouvez contourner cette restriction en construisant plusieurs tuyaux sur un même emplacement, cela compte alors comme plusieurs poses de tuyaux (l'exemple ci-dessous utilise 3 fois l'emplacement $3 \rightarrow 3$ ce qui compte comme 3 tuyaux). De même, le plan peut contenir des emplacements reliant le même point ($U = V$).
Exemple¶
Voici le plan de la machine :
Le noeud 1 (en bleu) est le départ, le noeud 2 (en rouge) est l'arrivée.
Le but est de refroidir de 7 degrés le liquide.
Le chemin $1 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 2$ a un refroidissement total de 7 avec 5 arêtes. C'est celui qui est le plus court ayant un refroidissement $\ge 7$.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : $N$, le nombre de points du plan.
- Sur la ligne suivante, un entier : $M$, le nombre d'emplacements possibles de tuyaux.
- Sur la ligne suivante, un entier : $K$, le nombre de degrés de refroidissement minimal du liquide à atteindre.
- Sur la ligne suivante, un entier : $A$, le point de départ.
- Sur la ligne suivante, un entier : $B$, le point d'arrivée.
- Sur les $M$ lignes suivantes :
- Un triplet d'entiers : $U_i$, $V_i$ et $W_i$ définissant les emplacements possibles des tuyaux. $U_i$ le point de départ, $V_i$ celui d'arrivée et $W_i$ le nombre de degrés de refroidissement du $i$-ème tuyau (rappel : le liquide ne peut passer que de $U_i$ vers $V_i$).
Sortie¶
S'il est impossible de réaliser un chemin satisfaisant ces conditions, afficher $-1$. Dans les autres cas, afficher le nombre de tuyaux minimum à utiliser pour satisfaire ces conditions.
Contraintes¶
- $1 \le N \le 20$
- $0 \le M \le 10^5$
- $1 \le K \le 100$
- $1 \le A, B, U_i, V_i \le N$
- $1 \le W_i \le 10^9$
Contraintes de performance¶
- $1 \le N \le 100$
- $1 \le K \le 10^6$