Skip to content
Sign in

フクロモモンガ (Sugar Glider)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
256 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

フクロモモンガの JOI 君が住んでいる森にはユーカリの木が \(N\) 本生えており，それらの木には \(1\) から \(N\) の番号がついている．木 \(i\) の高さは \(H_i\) メートルである．

JOI 君が相互に直接飛び移ることのできる木の組が \(M\) 組あり，各組の木の間を飛び移るためにかかる時間が定まっている．JOI 君が木の間を飛び移っている間は，地面からの高さが \(1\) 秒あたり \(1\) メートル下がる．すなわち，JOI 君の現在の地面からの高さが \(h\) メートル，木の間を飛び移るためにかかる時間が \(t\) 秒であるとき，飛び移った後の地面からの高さは \(h - t\) メートルとなる．ただし，\(h - t\) が \(0\) よりも小さくなる場合や行き先の木の高さよりも大きくなる場合は飛び移ることができない．

さらに，JOI 君は木の側面を上下に移動することによって，地面からの高さを \(0\) メートルから今いる木の高さの範囲で増減させることができる．JOI 君が地面からの高さを \(1\) メートル増加または減少させるためには \(1\) 秒の時間がかかる．

JOI 君は，木 \(1\) の高さ \(X\) メートルの位置から木 \(N\) の頂上 (高さ \(H_N\) メートルの位置) に行こうとしており，そのためにかかる時間の最小値を知りたい．

課題

各木の高さと，JOI 君が直接飛び移ることができる木の組の情報と，最初 JOI 君がいる場所の高さが与えられる．木 \(N\) の頂上に行くためにかかる時間の最小値を求めるプログラムを作成せよ.

Input

標準入力から以下のデータを読み込め．

  • \(1\) 行目には，整数 \(N, M, X\) が空白を区切りとして書かれている．これは，木の本数が \(N\) 本，移動できる木の組が \(M\) 組あり，最初 JOI 君が木 \(1\) の高さ \(X\) メートルの位置にいることを表す．
  • 続く \(N\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N\)) には，整数 \(H_i\) が書かれている．これは，木 \(i\) の高さが \(H_i\) メートルであることを表す．
  • 続く \(M\) 行のうちの \(j\) 行目 (\(1 \leqq j \leqq M\)) には，整数 \(A_j, B_j, T_j\) (\(1 \leqq A_j \leqq N\)，\(1 \leqq B_j \leqq N\)，\(A_j \neq B_j\)) が空白を区切りとして書かれている．これは，木 \(A_j\) と木 \(B_j\) の間を相互に \(T_j\) 秒で飛び移ることができることを表している．また，\(1 \leqq j < k \leqq M\) ならば，\((A_j, B_j) \neq (A_k, B_k)\) および \((A_j, B_j) \neq (B_k, A_k)\) を満たす．

Output

標準出力に，木 \(1\) の高さ \(X\) メートルの位置から木 \(N\) の頂上に行くためにかかる時間の最小値を秒単位で表す整数を \(1\) 行で出力せよ．ただし，そのような方法がない場合は代わりに \(-1\) を出力せよ．

Constraints

すべての入力データは以下の条件を満たす．

  • \(2 \leqq N \leqq 100\,000\)．
  • \(1 \leqq M \leqq 300\,000\)．
  • \(1 \leqq H_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N\))．
  • \(1 \leqq T_j \leqq 1\,000\,000\,000\) (\(1 \leqq j \leqq M\))．
  • \(0 \leqq X \leqq H_1\)．

Subtasks

小課題 1 [25 点]

以下の条件を満たす．

  • \(N \leqq 1\,000\)．
  • \(M \leqq 3\,000\)．
  • \(H_i \leqq 100\) (\(1 \leqq i \leqq N\))．
  • \(T_j \leqq 100\) (\(1 \leqq j \leqq M\))．

小課題 2 [25 点]

以下の条件を満たす．

  • \(X = 0\)．

小課題 3 [50 点]

追加の制限はない．

Examples

Sample input 1
5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20
Sample output 1
110

例えば，以下のように移動すればよい．

  1. 木 \(1\) を \(50\) メートル登る．
  2. 木 \(1\) から木 \(2\) に飛び移る．
  3. 木 \(2\) から木 \(4\) に飛び移る．
  4. 木 \(4\) から木 \(5\) に飛び移る．
  5. 木 \(5\) を \(10\) メートル登る．
Sample input 2
2 1 0
1
1
1 2 100
Sample output 2
-1

JOI 君は木 \(1\) から木 \(2\) に飛び移ることができない．

Sample input 3
4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10
Sample output 3
100

Notes

JOI 2014 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source