该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

路径翻转

题目描述

给定一个包含 $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$、$M$、$X$； 接下来 $M$行，每行输入两个整数 $u_i$、$v_i$，表示第 $i$条有向边从 $u_i$指向 $v_i$。

输出格式

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

样例

样例输入 1

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

样例输出 1

4

样例解释 1

通过以下操作序列达成目标，总成本为 $4$：

1. 花费 $1$从顶点 $1$移动到顶点 $2$；
2. 花费 $1$从顶点 $2$移动到顶点 $4$；
3. 花费 $1$从顶点 $4$移动到顶点 $3$；
4. 花费 $1$从顶点 $3$移动到顶点 $5$。

不存在总成本为 $3$或更小的方案，因此输出 $4$。

样例输入 2

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

样例输出 2

3

样例解释 2

通过以下操作序列达成目标，总成本为 $3$：

1. 花费 $1$从顶点 $1$移动到顶点 $2$；
2. 花费 $1$执行翻转操作，反转所有边的方向；
3. 花费 $1$从顶点 $2$移动到顶点 $5$。

不存在总成本为 $2$或更小的方案，因此输出 $3$。

样例输入 3

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

样例输出 3

4294967299

样例解释 3

答案可能超过 32 位整数范围，需注意使用 64 位整数类型（如 C++ 的 long long）处理。

样例输入 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, v_i \leq N$（$1 \leq i \leq M$）
• 所有输入值均为整数
• 保证存在从顶点 $1$到顶点 $N$的操作序列

子任务