工作规划
题目描述
n 台机器人正在完成任务。其中，第 i 台机器人需要工作 ti 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m条，每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。
请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。
输入格式
第一行：两个整数 n 和 m
第二行到第 n+1 行：每个机器人需要的时间 ti
接下来 m 行：每行有两个整数 a 和 b，表示第 b 台机器人必须要等第 a 台机器人任务完成之后才能开始工作。
输出格式
单个整数，表示所有机器人任务完成最少需要花多少时间。
输入样例
10 9 3 29 1 35 18 22 8 29 4 12 3 2 4 8 1 7 6 5 7 10 8 1 10 9 2 4 5 3
输出样例
161
说明提示
1≤n≤104
1≤m≤50,000
1≤ti≤105
1≤ai,bi≤n
限制
时间限制：1000ms
内存限制：512MiB
相似题推荐
专属教室
题目描述
在一所学校中，有 N 个班级，每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si，但学校计划将其调整到新的教室 Ti。
已知所有班级当前使用的教室编号互不相同，所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室，且一次只能安排一个班级进行更换。在更换时，目标教室必须是空闲的。
学校希望找到一个合理的更换顺序，使得所有班级都能顺利迁入目标教室。请判断是否可能。
输入格式
第一行一个整数 N。
接下来 N 行，每行两个字符串 Si 和 Ti，表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。
输出格式
如果存在一种顺序使得所有班级都能完成更换，输出 Yes，否则输出 No。
输入样例#1
2 b m m d
输出样例#1
Yes
输入样例#2
3 a b b c c a
输出样例#2
No
说明提示
1≤N≤105
Si,Ti 为由小写英文字母组成的字符串，长度在 1 到 8 之间。
Si≠Ti
所有 Si 互不相同。
所有 Ti 互不相同。
限制
时间限制：1000ms
内存限制：256MiB
