Damaged Bicycle

题目来源

CCPC Harbin 2021 G

题目描述

校园可以被看成 $n$ 个点，$m$ 条双向边的图，其中第 $i$ 条边的长度是 $w_i$。你的宿舍在 $1$ 号点，教学楼在 $n$ 号点，你想从宿舍去教学楼。你的走路速度是每秒 $t$，骑车速度是每秒 $r$。

根据共享单车app，校园内一共有 $k$ 个停车点。第 $i$ 个停车点在 $a_i$ 点，但是有 $\frac{p_i}{100}$ 的概率，车可能是坏的。但是你只有到达 $a_i$ 点，然后扫描二维码之后才能知道第 $i$ 辆车是不是好的。如果车是好的，那就可以骑到终点。

问你最优策略下，你最小的到达终点的期望时间是多少。如果到达不了 $n$ 号点，输出 -1。

输入格式

第一行包含两个整数 $t, r (1\leq t \leq r \leq 10^4)$ 表示走路和骑车的速度。

接下来一行，包含两个整数 $n, m (1\leq n, m \leq 10^5)$，表示点的个数和边的个数。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i (1\leq u_i, v_i \leq n, u_i\neq v_i, 1\leq w_i \leq 10^4)$，表示 $u_i$ 和 $v_i$ 之间有一条长度为 $w_i$ 的双向边。

接下来一行一个整数 $k (0\leq k \leq 18)$，表示自行车的个数。

接下来 $k$ 行，每行两个整数 $a_i, p_i (1\leq a_i \leq n, 0\leq p_i \leq 100)$，表示自行车的位置和对应自行车损坏的概率。

保证所有自行车的位置都不同。

输出格式

如果无法到达，输出 -1，否则输出最小的期望时间，相对误差或者绝对误差不超过 $10^{-6}$ 即可。

样例输入 1

3 15
4 3
1 2 600
1 3 300
2 4 900
1
3 50

样例输出 1

460.000000

样例输入 2

3 15
5 4
1 2 600
1 3 300
2 5 900
3 4 3
2
3 50
4 0

样例输出 2

220.600000

样例输入 3

3 15
5 4
1 2 600
1 3 300
4 5 900
3 2 300
2
3 50
4 0

样例输出 3

-1

样例解释

对于第一个样例，一种可能的策略是：

• 沿着路线 $1\rightarrow 3$ 尝试骑校园里唯一的自行车。
• 如果自行车损坏了，就沿着路线 $3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ 步行，或者骑自行车。

考虑到路上的时间成本：

如果自行车损坏了，你会沿着路线 $1\rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ 步行，总长度是 $2100$。所以时间成本是 $\frac{2100}{3} = 700$。

如果自行车没有损坏，你会沿着路线 $1\rightarrow 3$ 步行，总长度是 $300$，然后骑自行车沿着路线 $3 \rightarrow 1 \rightarrow 2 \rightarrow 4$，总长度是 $1800$。所以时间成本是 $\frac{300}{3} + \frac{1800}{15} = 220$。

自行车有 $\frac{50}{100}$ 的概率损坏。所以期望时间成本是 $\frac{50}{100} \times 700 + (1 - \frac{50}{100}) \times 220 = 460$。