D - Safe Climbing Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は山岳地帯をハイキングすることにしました。この山岳地帯には N 個の地点と M 本の登山道があり、各登山道は双方向に通行できます。高橋君は地点 1 にある登山口から地点 N にある山頂を目指しています。

各地点 i (1 \leq i \leq N) には「危険度」P_i が設定されています。これは、その地点における落石や崖崩れなどの自然災害のリスクの高さを表す指標です。また、j 番目 (1 \leq j \leq M) の登山道は地点 U_j と地点 V_j を双方向に結んでおり、通過するのに時間 W_j がかかります。なお、地点での滞在時間は考えないものとします。

高橋君は地点 1 から出発し、登山道を繰り返したどって地点 N に到着します。このとき、同じ地点や同じ登山道を複数回通ることも許されます。経路の所要時間は、通過した登山道の時間の合計とします。また、経路の危険度は、出発地点 1 と到着地点 N を含む、経路上で訪れるすべての地点の危険度の最大値とします。

高橋君はできるだけ安全にハイキングを楽しみたいと考えていますが、日没までに山頂に到着する必要があります。具体的には、所要時間が T 以下であるような経路の中で、経路の危険度を最小化したいです。

地点 1 から地点 N まで所要時間 T 以下で到達できる経路が少なくとも1つ存在することが保証されます。条件を満たす経路における危険度の最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^4
  • 1 \leq M \leq 4 \times 10^4
  • 1 \leq T \leq 10^9
  • 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
  • 同じ2地点を結ぶ登山道が複数存在することがある。
  • 地点 1 から地点 N まで所要時間 T 以下で到達できる経路が少なくとも1つ存在する。
  • 入力はすべて整数である。

入力

N M T
P_1 P_2 \ldots P_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、地点の数 N 、登山道の数 M 、所要時間の上限 T が、スペース区切りで与えられる。
  • 2 行目には、各地点の危険度 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。P_i は地点 i の危険度を表す。
  • 3 行目から 2 + M 行目までの M 行では、各登山道の情報が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、j 番目の登山道が結ぶ2地点 U_j, V_j と、通過にかかる時間 W_j が、スペース区切りで与えられる。

出力

所要時間が T 以下である経路における危険度の最小値を 1 行で出力せよ。

入力例 1

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

出力例 1

5

入力例 2

5 7 9
3 8 2 7 4
1 2 10
1 2 3
2 5 6
1 3 2
3 4 2
4 5 6
3 5 9

出力例 2

8

入力例 3

10 18 25
10 30 5 40 20 15 60 25 35 12
1 2 5
2 10 15
1 3 4
3 6 7
6 10 12
3 4 3
4 10 5
1 5 10
5 8 5
8 10 9
2 5 2
5 6 2
6 7 3
7 10 3
2 3 8
4 8 2
8 9 4
9 10 4

出力例 3

15

入力例 4

20 40 100
50 12 80 7 30 65 18 90 22 55 5 70 35 42 15 100 28 60 10 40
1 2 10
2 4 10
4 7 8
7 11 12
11 15 10
15 19 9
19 20 8
1 3 5
3 6 5
6 10 15
10 14 10
14 20 20
1 5 20
5 9 10
9 13 15
13 17 10
17 20 20
2 5 6
5 7 7
7 9 5
9 11 6
11 13 7
13 15 5
15 17 6
17 19 4
3 8 12
8 12 8
12 16 10
16 20 25
4 8 20
6 12 15
10 16 10
14 18 6
18 20 10
2 6 30
5 10 25
9 14 20
13 18 12
3 4 50
12 19 30

出力例 4

50

入力例 5

2 1 1000000000
0 1000000000
1 2 1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi has decided to go hiking in a mountainous area. This area consists of N points and M trails, where each trail can be traversed in both directions. Takahashi starts at the trailhead at point 1 and aims to reach the summit at point N.

Each point i (1 \leq i \leq N) has a "danger level" P_i assigned to it. This represents the level of risk of natural disasters such as rockfalls or landslides at that point. Additionally, the j-th (1 \leq j \leq M) trail bidirectionally connects point U_j and point V_j, and it takes W_j time to traverse. We assume that the time spent staying at any point is negligible.

Takahashi starts from point 1 and repeatedly traverses trails to reach point N. He is allowed to visit the same point or traverse the same trail multiple times. The travel time of a route is the sum of the times of the traversed trails. The danger level of a route is the maximum danger level among all points visited along the route, including the start point 1 and the destination point N.

Takahashi wants to enjoy hiking as safely as possible, but he must reach the summit before sunset. Specifically, he wants to minimize the danger level of the route among all routes whose travel time is at most T.

It is guaranteed that there is at least one route from point 1 to point N with a travel time of at most T. Find the minimum possible danger level of a route satisfying the conditions.

Constraints

  • 2 \leq N \leq 2 \times 10^4
  • 1 \leq M \leq 4 \times 10^4
  • 1 \leq T \leq 10^9
  • 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
  • There may be multiple trails connecting the same pair of points.
  • There is at least one route from point 1 to point N with a travel time of at most T.
  • All input values are integers.

Input

N M T
P_1 P_2 \ldots P_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of points N, the number of trails M, and the maximum travel time T, separated by spaces.
  • The second line contains the danger levels of each point P_1, P_2, \ldots, P_N, separated by spaces. P_i represents the danger level of point i.
  • The next M lines, from the 3rd line to the (2 + M)-th line, provide information about each trail.
  • The (2 + j)-th line (1 \leq j \leq M) contains the two points U_j and V_j connected by the j-th trail, and the travel time W_j, separated by spaces.

Output

Print the minimum danger level of a route with a travel time of at most T in a single line.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

5 7 9
3 8 2 7 4
1 2 10
1 2 3
2 5 6
1 3 2
3 4 2
4 5 6
3 5 9

Sample Output 2

8

Sample Input 3

10 18 25
10 30 5 40 20 15 60 25 35 12
1 2 5
2 10 15
1 3 4
3 6 7
6 10 12
3 4 3
4 10 5
1 5 10
5 8 5
8 10 9
2 5 2
5 6 2
6 7 3
7 10 3
2 3 8
4 8 2
8 9 4
9 10 4

Sample Output 3

15

Sample Input 4

20 40 100
50 12 80 7 30 65 18 90 22 55 5 70 35 42 15 100 28 60 10 40
1 2 10
2 4 10
4 7 8
7 11 12
11 15 10
15 19 9
19 20 8
1 3 5
3 6 5
6 10 15
10 14 10
14 20 20
1 5 20
5 9 10
9 13 15
13 17 10
17 20 20
2 5 6
5 7 7
7 9 5
9 11 6
11 13 7
13 15 5
15 17 6
17 19 4
3 8 12
8 12 8
12 16 10
16 20 25
4 8 20
6 12 15
10 16 10
14 18 6
18 20 10
2 6 30
5 10 25
9 14 20
13 18 12
3 4 50
12 19 30

Sample Output 4

50

Sample Input 5

2 1 1000000000
0 1000000000
1 2 1000000000

Sample Output 5

1000000000