AT_abc395_e [ABC395E] Flip Edge

给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。第 $i$ 条边（$1 \leq i \leq M$）从顶点 $u_i$ 指向顶点 $v_i$。 初始时，你位于顶点 $1$，需要通过重复以下操作到达顶点 $N$： - 选择以下两种操作之一： - **移动操作**：从当前顶点沿边移动到相邻顶点，成本为 $1$。具体来说，设当前顶点为 $v$，选择一条从 $v$ 指向 $u$ 的边，移动到顶点 $u$。 - **翻转操作**：反转所有边的方向，成本为 $X$。具体来说，在操作前存在的每条从 $v$ 到 $u$ 的边，在操作后将变为从 $u$ 到 $v$ 的边，反之亦然。 题目保证存在从顶点 $1$ 到顶点 $N$ 的操作序列。 请计算到达顶点 $N$ 所需的最小总成本。

输入通过标准输入给出，格式如下： > $N$ $M$ $X$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_M$ $v_M$

输出到达顶点 $N$ 的最小总成本。

### 约束条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $1 \leq X \leq 10^9$ - $1 \leq u_i \leq N$（$1 \leq i \leq M$） - $1 \leq v_i \leq N$（$1 \leq i \leq M$） - 输入均为整数 ### 样例解释 1 给定图的示意图（图片链接略）。通过以下操作序列，总成本为 $4$： - 花费 $1$ 移动到顶点 $2$ - 花费 $1$ 移动到顶点 $4$ - 花费 $1$ 移动到顶点 $3$ - 花费 $1$ 移动到顶点 $5$ 无法以 $3$ 或更小的总成本到达顶点 $5$，因此输出 `4`。 ### 样例解释 2 图的边与样例 1 相同，但翻转成本不同。通过以下操作序列，总成本为 $3$： - 花费 $1$ 移动到顶点 $2$ - 花费 $1$ 执行翻转操作 - 花费 $1$ 移动到顶点 $5$ 无法以 $2$ 或更小的总成本到达顶点 $5$，因此输出 `3`。 ### 样例解释 3 答案可能超过 32 位整数范围，需注意处理大数。 翻译由 DeepSeek R1 完成