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 完成