Cuisine – Regional event 2015

Level 5

É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.

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4
1 1 10
2 2 1 3 5
0
0
Sample output
15
Note

Pour faire cuire des pâtes, il faut faire chauffer pendant 10 minutes la casserole contenant de l’eau bouillante et des pâtes. Pour obtenir cette casserole il faut mélanger des pâtes, ce qui vous prend une minute à verser puisque vous êtes lent, et de l’eau qu’il vous a pris 5 minutes de faire bouillir.

Vous avez donc besoin en tout de 15 minutes pour faire des pâtes.

Sample input
25
0
1 0 10
0
2 2 1 1 1
0
1 4 5
0
3 3 1 6 1 5 1
0
1 8 5
0
0
4 11 1 9 1 6 1 10 1
1 12 2
1 13 10
1 8 2
2 15 0 14 0
0
1 17 4
0
0
4 19 1 20 1 18 1 2 1
2 21 0 15 0
3 22 1 16 1 7 1
1 23 10
Sample output
29
Note

Maintenant vous vous attaquez à une recette plus difficile : une tarte au citron meringuée. La recette peut être simplifiée par le schéma suivant :

Tarte au citron meringuée

Submit your solution

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