Prologin
2018
Énoncé¶
Vous souhaitez réaliser un livre de cuisine. Votre grand-mère vous a donné toutes ses recettes, il vous faut maintenant les rédiger correctement en indiquant toutes les informations récapitulatives de chaque recette.
En particulier, vous aimeriez bien indiquer le temps de préparation de chaque recette. Vous savez, pour chaque étape de la recette, de quelles autres étapes elle dépend et combien de temps est nécessaire pour passer d’une étape à l’autre.
La réponse à tout étant un programme informatique, vous vous attelez à la tâche d’écrire un programme qui fait ce calcul pour vous.
Entrée¶
L’entrée comprendra :
- sur la première ligne, le nombre N d’étapes dans la recette ;
- sur les N lignes suivantes, représentant chacune une étape i (avec i allant de 0 à N - 1, dans l’ordre croissant), la liste des dépendances de cette étape : d’abord le nombre Mi de dépendances de cette étape, puis une espace, puis le numéro de la première étape dont dépend i, puis une espace, puis le temps nécessaire pour passer de cette étape à i, puis une espace, puis le numéro de la seconde étape dont dépend i, puis une espace, puis le temps nécessaire pour passer de cette étape à i…
Sortie¶
Vous afficherez en sortie :
- le temps minimal pour réaliser la recette.
Contraintes¶
- 2 ≤ N ≤ 10 000 ;
- il ne peut pas y avoir de boucle : une étape ne peut pas dépendre, après lui avoir rajouté en dépendance celles des étapes dans elle dépend, d’elle-même.
