标题: 盛夏的果实 [打印本页] 作者: admin 时间: 2018-7-10 16:20 标题: 盛夏的果实 【问题描述】
丛林中共有 n 棵果树，每一棵果树上都有数量不等的果实。果树之间有单向边连接。你提着一个篮子从编号为 1 的果树出发，选择一条路径走到编号为 n 的果树。每当你走到一棵果树的时候，你都会将这棵果树的所有果实采摘下来，放入篮子中，假设这个过程是不花费任何时间的。而当你在路上行走的时候，每走 1 分钟，你都会从篮子中拿出一个果实吃掉（如果篮子里还有果实的话）。
你的任务是求出你所携带的篮子至少要能够承担多少个果实的重量，才能够顺利地选择一条路径完成旅途，并且在途中不扔掉任何果实。（当到达第 i 棵果树时，还是要将这棵果树的全部果实放入篮子中）。
【输入格式】
第一行为两个整数 n 和 m，分别表示果树的个数与单向边的条数。所有的果树从 1 到 n 编号。
接下来一行，n 个用空格隔开的整数，分别表示编号 1~n 的果树上果实的个数。
接下来 m 行，每行三个用空格隔开的整数 x,y,c，表示从 x 到 y 有一条单向边相连，这条边通过所需的时间为 c（分钟）。