任务

Grade 100 Open Time Wednesday, 17 June 2020, 9:30 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:30 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:30 PM
Input file chore.in Output file chore.out

【题目描述】任务(chore)POJ 1949

有n个任务,第i个任务需要时间timei(时间不超过100)来完成,并且第i个任务必须在它“前面的”某些任务完成之后才能开始。问最短需要多少时间来完成任务。

【输入格式】

第一行一个整数n(3≤N≤10 000),表示完成的任务数。

随后2~n+1行,依次描述每个任务的相关信息,即每行第一个整数表示完成该任务需要的时间,第二个整数表示完成该任务前先要完成的任务数,随后是先要完成的任务的编号。

【输出格式】

输出完成所有任务的最短时间。

【输入样例】

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

【样例说明】

任务1开始于时间0,结束于时间5;

任务2开始于时间5,结束于时间6;

任务3开始于时间6,结束于时间9;

任务4开始于时间5,结束于时间11;

任务5开始于时间11,结束于时间12;

任务6开始于时间11,结束于时间19;

任务7开始于时间19,结束于时间23。