题解：abc395_e E - Flip Edge

xyx404 · 2025-03-01 22:44:17 · 题解

题意：

给定一个有向图，我们从顶点 1 出发，想要到达顶点 N。

有两种操作：

1. 沿着有向边移动到下一个顶点，花费为 1。
2. 反转所有边的方向，花费为 X。

我们的目标是找到到达 N 的最小总花费。

思路：

最短路，迪杰斯特拉。

只需要改建图就行了。

建图：

每个顶点 u 在原图和反转图中被分别表示为两个节点 2 \times u 为状态 0 原图和 2 \times u+1 为状态 1 反转图。

原图边：对于原边 u 到 v，在状态 0 中添加边 2 \times u 到 2 \times v 代价为 1。

反转边：对于原边 u 到 v，在状态 1 中添加边 2 \times v+1 到 2 \times u+1 代价为 1。

状态切换边：每个顶点 u 在两种状态间添加 2 \times u 到 2 \times u + 1 的双向边，代价为 X。

之后照常跑迪杰斯特拉就行了。

因为每个点都被分成了两个，所以最后输出要在两个终点中取最小值。

提交记录和代码。