问题2103--家务琐事

2103: 家务琐事

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 6
[提交] [状态] [讨论版] [命题人:]

题目描述

约翰有一份必须完成的N （3≤N ≤10000）个家务的清单。每个家务都需要一个整数时间T （1≤T ≤100）才能完成，并且可能还有其他家务必须在这个家务开始之前完成。至少有一个家务没有先决条件：第1号。家务K （K >1）只能以家务1～K-1作为先决条件。计算完成所有N 个家务所需的最少时间。当然，可以同时进行彼此不依赖的家务。

输入

第1行包含一个整数N 。第2～N +1行描述每个家务，第2行包含家务1；第3行包含家务2，以此类推。每行都包含完成家务的时间、先决条件的数量Pi （0≤Pi ≤100）和Pi 个先决条件。

输出

单行输出完成所有家务所需的最少时间。

样例输入 Copy 

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

样例输出 Copy 

23

来源/分类

关键路径 
[提交] [状态]