D - Mountain Hiking Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は山岳地帯でのハイキングを計画しています。この山岳地帯には N 個の地点があり、地点 i (1 \leq i \leq N) の標高は H_i です。

地点と地点の間には M 本の登山道が存在し、j 番目 (1 \leq j \leq M) の登山道は地点 U_j と地点 V_j を双方向に結んでいます。j 番目の登山道を1回通るときの疲労度は、両端の地点の標高差の絶対値 |H_{U_j} - H_{V_j}| です。

高橋君は地点 1（出発地点）から地点 N（目的地）まで、登山道のみを使って移動します。移動の際、同じ地点を複数回訪れたり、同じ登山道を複数回通ったりすることも許されます。同じ登山道を複数回通った場合は、通るたびにその登山道の疲労度が加算されます。

ただし、疲労度が K 以下の登山道のみ通ることができます。疲労度が K より大きい登山道は通ることができません。

通行可能な登山道のみを使って地点 1 から地点 N まで移動するとき、通った登山道の疲労度の合計の最小値を求めてください。

通行可能な登山道のみを使って地点 1 から地点 N まで到達できない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 同じ地点の組を結ぶ登山道は高々 1 本である（多重辺はない）
  • 入力はすべて整数である

入力

N M K
H_1 H_2 \ldots H_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、地点の数 N、登山道の数 M、1 本の登山道あたりの疲労度の上限 K が、スペース区切りで与えられる。
  • 2 行目には、各地点の標高 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 3 行目から M+2 行目までの M 行では、登山道の情報が与えられる。
  • そのうち j 行目（3 行目から数えて j 番目）では、j 番目の登山道が結ぶ 2 つの地点の番号 U_j と V_j が、スペース区切りで与えられる。

出力

通行可能な登山道のみを使って地点 1 から地点 N まで移動できる場合、疲労度の合計の最小値を 1 行で出力してください。到達できない場合は -1 を出力してください。

入力例 1

5 6 5
10 14 8 12 16
1 2
1 3
2 4
3 4
2 5
4 5

出力例 1

6

入力例 2

4 4 3
0 10 20 30
1 2
2 3
3 4
1 4

出力例 2

-1

入力例 3

7 10 10
0 8 5 15 12 20 25
1 2
1 3
2 4
3 4
3 5
4 6
5 6
5 7
6 7
2 5

出力例 3

25

Score : 400 pts

Problem Statement

Takahashi is planning a hike in a mountainous area. There are N locations in this mountainous area, and the elevation of location i (1 \leq i \leq N) is H_i.

There are M trails between locations, and the j-th (1 \leq j \leq M) trail bidirectionally connects location U_j and location V_j. The fatigue cost of traversing the j-th trail once is the absolute difference in elevation between its two endpoints, |H_{U_j} - H_{V_j}|.

Takahashi will travel from location 1 (the starting point) to location N (the destination) using only trails. During the trip, he is allowed to visit the same location multiple times and traverse the same trail multiple times. If the same trail is traversed multiple times, its fatigue cost is added each time it is traversed.

However, he can only use trails whose fatigue cost is at most K. Trails with fatigue cost greater than K cannot be used.

Find the minimum total fatigue cost when traveling from location 1 to location N using only passable trails.

If it is impossible to reach location N from location 1 using only passable trails, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • There is at most one trail connecting any pair of locations (no multiple edges)
  • All input values are integers

Input

N M K
H_1 H_2 \ldots H_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains the number of locations N, the number of trails M, and the upper limit on fatigue cost per trail K, separated by spaces.
  • The second line contains the elevations H_1, H_2, \ldots, H_N of each location, separated by spaces.
  • The following M lines (from the 3rd line to the (M+2)-th line) contain information about the trails.
  • The j-th of these lines contains the numbers U_j and V_j of the two locations connected by the j-th trail, separated by spaces.

Output

If it is possible to travel from location 1 to location N using only passable trails, output the minimum total fatigue cost on a single line. If it is impossible to reach the destination, output -1.

Sample Input 1

5 6 5
10 14 8 12 16
1 2
1 3
2 4
3 4
2 5
4 5

Sample Output 1

6

Sample Input 2

4 4 3
0 10 20 30
1 2
2 3
3 4
1 4

Sample Output 2

-1

Sample Input 3

7 10 10
0 8 5 15 12 20 25
1 2
1 3
2 4
3 4
3 5
4 6
5 6
5 7
6 7
2 5

Sample Output 3

25