首页 > 试题广场 >

任务调度

[编程题]任务调度
  • 热度指数：54 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在公司的工作安排中，不同的工作可能是互相独立的，也可能是有依赖的。一个任务A是另外一个任务B的前置任务，要A完成后才能进行B，特别地，每个任务可能最多有2个前置任务，而前置任务本身可能也有前置任务。

这样的前置依赖结构可以用树表示，子节点是父节点的前置任务

当有一系列任务分配下来后，由于项目规划的需要，问当最后一个任务（根节点）完成，最少需要多少时间


输入描述:
第一行两个正整数m, n，分别代表总共有树上有m个节点，和树上有n条边，用空格分割
下面有m个行，表示每个节点任务的id和所需要的时间，用空格分割
下面有n行，每行为3个部分，表示树上的边，用空格分割，第一个数字为某非叶子节点（父节点）的id, 第二个为该边为left还是right，第三个为子节点的id
注意：id彼此不会重复，id 1为根节点，2<=m<=1000,  1<=n<=1000，任务时间每个不会大于1000


输出描述:
一个整数，表示最后一个任务（根节点）完成，最少需要多少时间
示例1

输入

10 9
1 10 
2 20 
3 25 
4 239 
5 41 
6 50 
7 61 
8 72 
9 35
10 41
1 left 2
1 right 3
2 left 4
2 right 5
3 left 6
6 left 7
6 right 8
7 left 9
7 right 10

输出

269

说明

如上图所示，最后总的最优时间为10+20+239=269
算法知识视频讲解
添加回答
LiuGuohui头像 LiuGuohui
都是算法问题吗
发表于 2021-02-23 22:18:35 回复(0)
提交观点

问题信息

运维工程师 网易 游戏研发工程师 2021
上传者：小小
难度：
1条回答 2706浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号