分数: 425 点
问题陈述
给你一个有向图 N 顶点和 M 边缘。 的 i第边缘 (1 \leq i \leq M) 是从顶点开始的有向边 u _ i 到顶点 v _ i.
最初,您位于顶点 1。您要重复以下操作,直到到达顶点 N:
- 执行以下两项操作之一:
- 从当前顶点沿着有向边移动。这会产生以下费用 1。更准确地说,如果你在顶点 v,选择一个顶点 u 这样有一个有向边 v to u,并移动到顶点 u.
- 反转所有边缘的方向。这会产生以下费用 X。更准确地说,当且仅当存在一条有向边 v to u 在此操作之前,有一个有向边 执行此操作后立即 u to v 。
保证对于给定的图,您可以到达顶点 N 从顶点 1 通过重复这些操作。
找到到达顶点所需的最小总成本 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)
- 对于给定的图,保证您可以到达顶点 N 从顶点 1 所描述的操作。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
输出
打印到达顶点所需的最小总成本 N.
示例输入 1
5 6 5 1 2 2 4 3 1 3 5 4 3 5 2
示例输出 1
4
给定的图表如下所示:

你可以到达顶点 5 总成本为 4 通过执行以下操作:
- 移动到顶点 2 成本为 1.
- 移动到顶点 4 成本为 1.
- 移动到顶点 3 成本为 1.
- 移动到顶点 5 成本为 1.
不可能到达顶点 5 总成本为 3 或更少,因此打印 4.
示例输入 2
5 6 1 1 2 2 4 3 1 3 5 4 3 5 2
示例输出 2
3
该图与示例 1 中的相同,但反转边的成本不同。
您到达顶点 5 的总成本为 3 如下:
- 移动到顶点 2 成本为 1.
- 反转所有边,代价为 1.
- 移动到顶点 5 成本为 1.
不可能到达顶点 5 总成本为 2 或更少,因此打印 3.
示例输入 3
8 7 613566756 2 1 2 3 4 3 4 5 6 5 6 7 8 7
示例输出 3
4294967299
请注意,答案可能会超出 32- 位整数范围。
示例输入 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