← 返回题目列表

AtCoder · abc395_e

H. 翻转边缘

中文机器翻译题面 查看原题

分数: 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