给定一个有向无环图 G=(V,E)。每个节点 v∈V 有分值 w(v),每条有向边 (u→v) 有时间花费 t(u,v)。起点为名为 start 的节点(w(start)=0),终点为所有名称以下划线“_”开头的节点。只能沿边方向前进。对从 start 到任一终点的可行路径 P,定义 Score(P)=∑w(v)−∑t(u,v)。请计算使 Score(P) 最大的路径的得分,并输出该最大值(可选:同时输出一条达到该最大值的路径)。请描述你的算法并给出时间与空间复杂度。
Sign in to leave a comment