题目描述

给定一个包含 $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$ 的最小总成本。

输入输出样例 #1

输入 #1

5 6 5
1 2
2 4
3 1
3 5
4 3
5 2

输出 #1

4

输入输出样例 #2

输入 #2

5 6 1
1 2
2 4
3 1
3 5
4 3
5 2

输出 #2

3

输入输出样例 #3

输入 #3

8 7 613566756
2 1
2 3
4 3
4 5
6 5
6 7
8 7

输出 #3

4294967299

输入输出样例 #4

输入 #4

20 13 5
1 3
14 18
18 17
12 19
3 5
4 6
13 9
8 5
14 2
20 18
8 14
4 9
14 8

输出 #4

21

说明/提示

约束条件

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

---

AtCoder 原题连接 {{ select(1) }}

• 写完了
• 还没写完