看到讨论和题解里说“因为时间单向流逝所以不可能成环”,但是这边自己想了想:
题目中允许重边存在,那么有可能存在一个点是一个环的一部分,绕这个环走一圈的时间(包括等待)与干等相同(比如不需要等并且边权都适当),同时这个点还有另一条唯一的出边走向终点且整个图只有起点、终点还有这个环,起点、终点与上面提到这个点直接相连。
这个时候再把 A , B , C 开一个合适的值,干等的代价就直接上天了,而绕圈的代价显然线性。
人话:可能存在结点 u 直接与 1 , n 连接且直接走 u−>n 需要等待,结点 u 同时在一个内向环中,通过构造数据使在这个内向环上走一圈的时间与直接在 u 等待相同且在环上的时间中总等待时间极小或为 0 。此时往环上跑一圈很可能优于直接等待。
求以上想法的正确性......