Pro.ID1644 Title关键路径 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1644 AC0 Submit0 Ratio- 时间&空间限制描述给出一个DAG ( directed acyclic praph 有向无环图 )，求从任意源点到任意汇点的最长路径的长度，即关键路径长度。 在此，定义“源点”为入度为0的顶点，“汇点”为出度为0的顶点。 输入第一行是两个正整数 n 和 e ( 1 ≤ n ≤ 600 , 1 ≤ e < 600 × 600 ) ，分别表示顶点个数和弧的数量。 接下来e行，每行3个整数 u , v 和 l ( 0 ≤ u, v < n , 0 ≤ l ≤ 1000 ) ，分别表示从顶点u到顶点v有一条弧，弧长度为 l 。 输出Description 给出一个DAG ( directed acyclic praph 有向无环图 )，求从任意源点到任意汇点的最长路径的长度，即关键路径长度。 在此，定义“源点”为入度为0的顶点，“汇点”为出度为0的顶点。 Input 第一行是两个正整数 n 和 e ( 1 ≤ n ≤ 600 , 1 ≤ e < 600 × 600 ) ，分别表示顶点个数和弧的数量。 接下来e行，每行3个整数 u , v 和 l ( 0 ≤ u, v < n , 0 ≤ l ≤ 1000 ) ，分别表示从顶点u到顶点v有一条弧，弧长度为 l 。 Output 输出一行结果：关键路径的长度。 Sample Input NULL Sample Output NULL Author 样例输入NULL 样例输出NULL 提示作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 03:18 , Processed in 0.015674 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
