正如之前的评论所说本题的质量不高,本题求的是节点 1 到 n+1 的最长路,但是题目的描述不清不楚。
为了体验游戏的完整性,小呆决定要看到所有的分支剧情——完成所有的任务。
你要告诉小呆完成整个游戏至少需要多少时间。
根据第一句话是否可以理解为要经过所有的节点,再根据第二句话和实际求的是否可以理解为节点 1 为游戏开始而节点 n+1 为游戏结束?
但实际上会出现从一个节点到节点 1 (角色死亡重开)和从节点 n+1 到一个节点(完结撒花时的回忆杀)的数据,好像也很合理( 。
所以根据上面说的朴素的拓扑排序是过不去的,要像题解中一样加一些另类的松弛操作才行,你问我怎么知道的,我只能说如果没有上面这些神奇的数据我第一发就过了。
但是对于本题的这种做法会导致最长路实际上没有经过部分节点,且这些节点实际上会使最长路更长,但只是因为在头节点前或在尾节点后导致不计算在内。
我主要想知道这题的数据是否违反了题目描述中的所有节点都应经过的说法,还是我语文理解太菜了应该从小学开始重修。(注:不在最长路但实际可经过的不算,且本题不存在环,即有向无环图)