翻译:
思路:
我们可以用 拓扑排序(TopoSort)(TopoSort)(TopoSort) 配合 动态规划(Dynamic Programming)(Dynamic\,\,Programming)(DynamicProgramming) 来解决这道题。可以把三元组 (a,b,x)(a,b,x)(a,b,x) 抽象成图中结点 aaa 到结点 bbb 的一条有向边,边权为 xxx。
先将输入数据存正向图以及它的反向图,并记录正向图中结点的入度,接着根据正向图进行拓扑排序,然后利用拓扑排序序列进行动态规划更新当前结点的答案。因为我们要求最早日期,所以可以用贪心思想,直接和每个 xxx 进行比较,这样能够得到最早日期。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码:
预计得分:100pts100pts100pts
预计时间超过:100%100\%100%用户