Damaged Bicycle

Problem Source

CCPC Harbin 2021 G

Problem Description

The campus can be viewed as a graph with $n$ vertices and $m$ bidirectional edges, where the $i$-th edge has length $w_i$. Your dormitory is at vertex $1$ and the teaching building is at vertex $n$; you want to go from the dormitory to the teaching building. Your walking speed is $t$ units per second, and your cycling speed is $r$ units per second.

According to the shared-bike app, there are $k$ bike-parking spots on campus. The $i$-th spot is at vertex $a_i$, but with probability $\frac{p_i}{100}$ the bike there may be broken. However, you only find out whether the $i$-th bike is good after arriving at vertex $a_i$ and scanning the QR code. If the bike is good, you can ride it to the destination.

Under the optimal strategy, what is the minimum expected time for you to reach the destination? If vertex $n$ cannot be reached, output -1.

Input Format

The first line contains two integers $t, r$ ($1 \le t \le r \le 10^4$), the walking and cycling speeds.

The next line contains two integers $n, m$ ($1 \le n, m \le 10^5$), the number of vertices and edges.

The next $m$ lines each contain three integers $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^4$), indicating a bidirectional edge of length $w_i$ between $u_i$ and $v_i$.

The next line contains an integer $k$ ($0 \le k \le 18$), the number of bikes.

The next $k$ lines each contain two integers $a_i, p_i$ ($1 \le a_i \le n$, $0 \le p_i \le 100$), the location of the bike and the probability that it is broken.

It is guaranteed that all bike locations are distinct.

Output Format

If the destination cannot be reached, output -1; otherwise output the minimum expected time. An absolute or relative error not exceeding $10^{-6}$ is acceptable.

Sample Input 1

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

Sample Output 1

460.000000

Sample Input 2

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

Sample Output 2

220.600000

Sample Input 3

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

Sample Output 3

-1

Sample Explanation

For the first sample, one possible strategy is:

• Follow the route $1 \rightarrow 3$ to try the only bike on campus.
• If the bike is broken, walk along the route $3 \rightarrow 1 \rightarrow 2 \rightarrow 4$, or ride a bike.

Considering the travel-time cost:

If the bike is broken, you walk along $1 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$, total length $2100$. So the time cost is $\frac{2100}{3} = 700$.

If the bike is not broken, you walk along $1 \rightarrow 3$, total length $300$, then ride the bike along $3 \rightarrow 1 \rightarrow 2 \rightarrow 4$, total length $1800$. So the time cost is $\frac{300}{3} + \frac{1800}{15} = 220$.

The bike is broken with probability $\frac{50}{100}$. So the expected time cost is $\frac{50}{100} \times 700 + (1 - \frac{50}{100}) \times 220 = 460$.