M - 素早い高橋君 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

AtCoder 国には 1 から N の番号がついた N 個の街と、1 から M の番号がついた M 本の道があります。 i 番目の道は街 X_i と Y_i を双方向に結んでおり、長さは C_i です。

高橋君ははじめ街 1 におり、スピード は 1 です。高橋君はスピードが s であるとき、長さ C の道を移動するのに \frac{C}{s} 時間かかります。

K 個の街 A_1,\ldots,A_K にはジムがあり、高橋君はジムで一回 T 時間トレーニングするごとにスピードを 1 上げることができます。
高橋君は訪れたそれぞれのジムで、0 回以上の好きな回数のトレーニングを行うことができます。

高橋君が街 N にたどり着くまでにかかる時間の最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq T \leq 10^6
  • 1 \leq X_i,Y_i \leq N
  • 1 \leq C_i \leq 10^6
  • 1 \leq A_1 < \ldots < A_K \leq N
  • 街 1 から街 N へ移動可能
  • 入力は全て整数である

入力

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

N M K T
X_1 Y_1 C_1
\vdots
X_M Y_M C_M
A_1 \dots A_K

出力

答えを出力せよ。

真の解との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

入力例 1

3 2 1 15
1 2 100
2 3 100
2

出力例 1

163.333333333333343

次のように行動することで \frac{490}{3}=163.333333\dots 時間で街 1 から街 3 へ移動することができます。

  • 道路 1 を使って街 1 から街 2 へ移動する。100 時間かかる。
  • 街 2 のジムでトレーニングする。15 時間かかり、スピードが 2 になる。
  • 街 2 のジムでトレーニングする。15 時間かかり、スピードが 3 になる。
  • 道路 2 を使って街 2 から街 3 へ移動する。\frac{100}{3} 時間かかる。

真の解との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定されるため、163.33321098 などの出力でも正解とみなされます。

入力例 2

5 5 3 2
1 3 1
3 2 10
2 5 10
1 4 10
4 5 10
2 3 4

出力例 2

11.666666666666668

入力例 3

5 5 3 2
1 3 1
3 2 10
2 5 10
1 4 8
4 5 10
2 3 4

出力例 3

11.333333333333332

Problem Statement

AtCoder Republic has N towns numbered 1 through N, and M roads numbered 1 through M. Road i connects towns X_i and Y_i bidirectionally, and its length is C_i.

Takahashi is initially at town 1 with speed 1. When his speed is s, traveling along a length-C road takes \frac{C}{s} hours.

K towns, towns A_1,\ldots,A_K, have a gym. Every time he works out once for T hours in a gym, his speed increases by 1.
He can work out any number of times (possibly zero) in each gym.

Find the minimum hours required for him to reach town N.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq T \leq 10^6
  • 1 \leq X_i,Y_i \leq N
  • 1 \leq C_i \leq 10^6
  • 1 \leq A_1 < \ldots < A_K \leq N
  • It is reachable from town 1 to town N.
  • All input values are integers.

Input

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

N M K T
X_1 Y_1 C_1
\vdots
X_M Y_M C_M
A_1 \dots A_K

Output

Print the answer.

Your answer is considered correct if the absolute or relative error from the true value is at most 10^{-6}.

Sample Input 1

3 2 1 15
1 2 100
2 3 100
2

Sample Output 1

163.333333333333343

The following moves allow him to travel from town 1 to 3 in \frac{490}{3}=163.333333\dots hours.

  • Travel from town 1 to 2 via road 1, spending 100 hours.
  • Work out in the gym at town 2 for 15 hours. Now his speed is 2.
  • Work out in the gym at town 2 for 15 hours. Now his speed is 3.
  • Travel from town 2 to 3 via road 2, spending \frac{100}{3} hours.

Sample Input 2

5 5 3 2
1 3 1
3 2 10
2 5 10
1 4 10
4 5 10
2 3 4

Sample Output 2

11.666666666666668

Sample Input 3

5 5 3 2
1 3 1
3 2 10
2 5 10
1 4 8
4 5 10
2 3 4

Sample Output 3

11.333333333333332