问题陈述
AtCoder Republic 有 N 城镇编号 1 通过 N,和 M 道路编号 1 通过 M。 道路 i 连接城镇 X_i 和 Y_i 双向,其长度为 C_i.
高桥最初在镇上 1 与 速度 1。当他的速度是 s,沿着长度行进-C 道路走 \frac{C}{s} 小时。
K 城镇,城镇 A_1,\ldots,A_K,有健身房。 每次他锻炼一次 T 在健身房里呆了几个小时,他的速度增加了 1.
他可以在每个健身房锻炼任意次数(可能为零)。
求他到达城镇所需的最短时间 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
以下动作允许他从城镇出发 1 to 3 in \frac{490}{3}=163.333333\dots 小时。
- 从城镇出发 1 to 2 经公路 1, 支出 100 小时。
- 在镇上的健身房锻炼身体 2 为 15 小时。 现在他的速度是 2.
- 在镇上的健身房锻炼身体 2 为 15 小时。 现在他的速度是 3.
- 从城镇出发 2 to 3 经公路 2, 支出 \frac{100}{3} 小时。
示例输入 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