题解：AT_abc395_e [ABC395E] Flip Edge

exLucas · 2025-03-02 08:15:31 · 题解

思路：

这一题直接跑 Dijkstra 算法就可以。但是由于存在反转边操作，我们需要额外记录当前图的边的方向状态。可以使用一个三元组 (u, d, dir) 来表示当前状态，其中 u 是当前所在的顶点，d是到达该顶点的最小花费，dir 表示当前图的边的方向状态,可以用 0 表示原始方向，1 表示反转后的方向。

具体来说跑最短路时只需要在板子上加上尝试反转当前边的代码就可以了。

复杂度：

• 时间复杂度：O((M + N)\log(N)) ，其中 N 是顶点数，M 是边数。
• 空间复杂度：O(M + N)

Code:

这么简单就不放了吧（