← 返回题目列表

AtCoder · past23_m

M. 升压高桥

中文机器翻译题面 查看原题

问题陈述

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