UOJ Logo Universal Online Judge

UOJ

#756. 【UNR #6】D1T1 加强版

附件下载 统计

“人在 UOI,刚下飞机”——hehe 蚤刚到下山市,便迫不及待地想和从各地赶来参加 UOI 的网友们面基。

下山市可以简化为一张 $n$ 个点 $m$ 条边的无向图,点用 $1$ 到 $n$ 标号,而第 $i$ 条边连接点 $u_i$ 和 $v_i$,长度为 $w_i$。

hehe 蚤初始在 $1$ 号点,他想要依次和 $k$ 个网友面基,第 $i$ 个网友初始在点 $p_i$。

hehe 蚤和网友们都是匀速走路的。hehe 蚤一秒可以走过 $a$ 单位长度,而他的网友们一秒可以走过 $b$ 单位长度。

当 hehe 蚤和一个或多个网友处于同一位置时,他们可以立刻面基,且面基不需要耗时。

hehe 蚤想知道,如果他和网友按照一个商量好的策略行动,那么他和所有网友顺次面基最少需要花费多少秒。

请注意,时间和边都是连续的,这意味着所有角色可以在边的中间面基、在边上折返和在点上或边中间停留,面基和折返等行动也可以发生在非整数秒。

输入格式

第一行为四个整数 $n, m, a, b$,依次为图的点数、边数,hehe 蚤的速度和网友们的速度。

接下来 $m$ 行每行有三个整数 $u_i, v_i, w_i$,表示有一条连接 $u_i$ 和 $v_i$ 且长度为 $w_i$ 的边。

接下来一行一个整数 $k$。

接下来一行, $k$ 个整数。其中第 $i$ 个表示第 $i$ 个网友初始所在位置。

输出格式

一个实数 $T$,表示最少的总时间。你只需要保证输出结果与答案绝对或相对误差不超过 $10^{-9}$ 即可被判为正确。

样例一

input

4 6 1 2
1 4 4
2 3 4
3 4 1
3 1 2
1 2 1
2 4 4
2
2 3

output

0.7500000000

样例二

input

4 6 2 1
1 4 4
2 3 4
3 4 1
3 1 2
1 2 1
2 4 4
2
2 3

output

1.1111111111

数据范围与提示

对于所有数据,保证 $2 \leq n \leq 10^5, n - 1 \leq m \leq 2 \times 10^5, 1 \leq k \leq 20, 1 \leq u, v, p_i \leq n, 1 \leq w \leq 10^6, 1\leq a, b\leq 10^6$;保证图连通且无自环、重边。

时间限制:$10\texttt{s}$

空间限制:$512\texttt{MB}$

目前 std 正确性未得到充分验证,如有疑问请联系 hehezhou。