P1113 Chores

Before milking the cows, John's farm has many chores to complete, each requiring a certain amount of time. For example: gathering the cows, driving them into the barn, cleaning their udders, and other tasks. It is necessary to finish all chores as early as possible to have more time to produce more milk. Of course, some chores must be done only after certain other chores are completed. For example, you can clean a cow’s udder only after driving it into the barn, and you cannot milk a cow before cleaning its udder. We call these the preparatory tasks for a given task. At least one task requires no preparatory work; the earliest task that can be started is labeled task $1$. John has a list of $n$ tasks to complete, and the list has a specific order: the preparatory tasks of task $k\ (k>1)$ can only be among tasks $1$ to $k-1$. Write a program that reads the description of each task in order and computes the minimum time needed to finish all tasks. Independent tasks can be executed simultaneously, and you may assume John's farm has enough workers to carry out any number of tasks in parallel.

- Line $1$: an integer $n\ (3 \le n \le 10{,}000)$, the number of tasks to complete. - Lines $2$ to $n+1$: each line contains space-separated integers, representing: - the task index (guaranteed to appear in strictly increasing order from $1$ to $n$ in the input file); - the time required to complete the task $len\ (1 \le len \le 100)$; - zero or more preparatory tasks, terminated by a single $0$. If a task has no preparatory tasks, it is described by a single $0$. There are no extra spaces anywhere in the input file.

Output a single integer: the minimum time required to complete all tasks.

Translated by ChatGPT 5