关键路径

题目内容

题目描述

给出一个有向图,图中每条有向边代表一个活动,每条边有一个权值,为该边所代表的活动需要消耗的时间。每个顶点代表活动的开始或结束事件。只有当指向一个顶点的所有边代表的活动都完成后,该顶点代表的事件才算完成,从而该顶点指向其他顶点的边代表的活动才能开始。从一个顶点出发的所有边代表的活动可以同时开始。求所有事件都完成,至少需要多少时间。

输入描述

输入的第一行为两个正整数,用空格隔开,分别代表事件的个数n,和活动的个数m。(1 <= n, m <= 105

接下来m行,每行3个正整数j k v,用空格隔开,代表一个活动是从第j个事件指向第k个事件,活动需要的时间是v。事件的编号从0开始。输入保证图中没有环。

输出描述

输出一行,代表所有事件都完成,至少需要的时间。

样例输入

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

样例输出

19

提示

提交评测
请登录后再操作

题目描述

关键路径
1169
0
Level3
21
17
81%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在