E - Flip Edge Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N 頂点 M 辺の有向グラフが与えられます。 i 番目 (1\leq i\leq M) の辺は頂点 u _ i から頂点 v _ i への有向辺です。

はじめ、あなたは頂点 1 におり、以下の操作を繰り返して頂点 N にたどり着きたいです。

  • 次の操作のうちのいずれかを行う。
    • 今いる頂点から辺をたどって移動する。コストが 1 かかる。より厳密には、今いる頂点を v として、v から u への有向辺が存在するような u を 1 つ選び、頂点 u へ移動する。
    • すべての辺の向きを反転する。コストが X かかる。より厳密には、この操作の直前に v から u への有向辺が存在しているとき、かつそのときに限り、この操作の直後に u から v への有向辺が存在する。

与えられるグラフにおいて、上の操作を繰り返して頂点 1 から頂点 N にたどり着くことができることが保証されます。

頂点 N にたどりつくまでにかかるコストの総和の最小値を求めてください。

制約

  • 2\leq N\leq2\times10 ^ 5
  • 1\leq M\leq2\times10 ^ 5
  • 1\leq X\leq10 ^ 9
  • 1\leq u _ i\leq N\ (1\leq i\leq M)
  • 1\leq v _ i\leq N\ (1\leq i\leq M)
  • 与えられるグラフにおいて、上記の操作を繰り返して頂点 1 から頂点 N にたどり着くことができる。
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

与えられたグラフは以下のようになります。

次のように操作を行うことで、コストの総和を 4 として頂点 5 にたどり着くことができます。

  • コストを 1 かけて頂点 2 に移動する。
  • コストを 1 かけて頂点 4 に移動する。
  • コストを 1 かけて頂点 3 に移動する。
  • コストを 1 かけて頂点 5 に移動する。

コストの総和を 3 以下として頂点 5 にたどり着くことはできないため、4 を出力してください。

入力例 2

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

出力例 2

3

与えられたグラフは入出力例 1 と同じですが、辺を反転させるのにかかるコストが異なります。

次のように操作を行うことで、コストの総和を 3 として頂点 5 にたどり着くことができます。

  • コストを 1 かけて頂点 2 に移動する。
  • コストを 1 かけてすべての辺を反転させる。
  • コストを 1 かけて頂点 5 に移動する。

コストの総和を 2 以下として頂点 5 にたどり着くことはできないため、3 を出力してください。

入力例 3

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

出力例 3

4294967299

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 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

Score : 425 points

Problem Statement

You are given a directed graph with N vertices and M edges. The i-th edge (1 \leq i \leq M) is a directed edge from vertex u _ i to vertex v _ i.

Initially, you are at vertex 1. You want to repeat the following operations until you reach vertex N:

  • Perform one of the two operations below:
    • Move along a directed edge from your current vertex. This incurs a cost of 1. More precisely, if you are at vertex v, choose a vertex u such that there is a directed edge from v to u, and move to vertex u.
    • Reverse the direction of all edges. This incurs a cost of X. More precisely, if and only if there was a directed edge from v to u immediately before this operation, there is a directed edge from u to v immediately after this operation.

It is guaranteed that, for the given graph, you can reach vertex N from vertex 1 by repeating these operations.

Find the minimum total cost required to reach vertex N.

Constraints

  • 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)
  • For the given graph, it is guaranteed that you can reach vertex N from vertex 1 by the operations described.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M X
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

Output

Print the minimum total cost required to reach vertex N.

Sample Input 1

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

Sample Output 1

4

The given graph looks like this:

You can reach vertex 5 with a total cost of 4 by doing the following:

  • Move to vertex 2 at a cost of 1.
  • Move to vertex 4 at a cost of 1.
  • Move to vertex 3 at a cost of 1.
  • Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 3 or less, so print 4.

Sample Input 2

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

Sample Output 2

3

The graph is the same as in Sample 1, but the cost to reverse edges is different.

You can reach vertex 5 with a total cost of 3 as follows:

  • Move to vertex 2 at a cost of 1.
  • Reverse all edges at a cost of 1.
  • Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 2 or less, so print 3.

Sample Input 3

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

Sample Output 3

4294967299

Note that the answer may exceed the 32-bit integer range.

Sample Input 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

Sample Output 4

21