题目描述(ID:12168)
标题: Chores
标签: 动态规划 图结构 拓扑排序 最短路
详情:

农夫约翰的家人在挤牛奶的时候都在做农务,尽可能快完成所有农务。但是有些农务必须在别的农物完成之后才能开始。


农民约翰有一个必须完成的N项农务(3小于=N=10,000)的列表。每个农务都需要一个整数时间(1小于=100的时间小于=100)才能完成,并且在开始这项农务之前,还可能需要完成其他的农务。我们将把这些称为“先决条件”。当然,至少有一项农务没有先决条件。而有些农物有可能有K个先决条件。写一个程序,计算完成所有N个农务所需的最短时间。当然,不依赖于彼此的农务可以同时进行。

输入格式:
第一行一个整数n,表示有n项农务。
接下来n行,分别表示农务编号为1~n。每行有几个整数,用空格隔开。每行第一个整数位该项农务所需要话费的时间,第二个整数k表示,该项农务有k个先决条件,接下k整数便是这些先决条件的农务编号 Pi, (0 <= Pi <= 100)。
输出格式:
只有一行,为完成所有农务的最短时间。
样例:

输入

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

输出

23

解释

[Here is one task schedule:

Chore 1 starts at time 0, ends at time 5.

Chore 2 starts at time 5, ends at time 6.

Chore 3 starts at time 6, ends at time 9.

Chore 4 starts at time 5, ends at time 11.

Chore 5 starts at time 11, ends at time 12.

Chore 6 starts at time 11, ends at time 19.

Chore 7 starts at time 19, ends at time 23.

]
登录并解答