### HUST Past Monthly Hard Problems Challenge Contest (1)

From: 2011-05-13 12:00:00 To: 2011-05-13 17:00:00 Now: 2017-09-20 01:07:33 Status: Public

# G - The expected distance

Time Limit: 3s Memory Limit: 128MB

Submissions: 58 Solved: 3
Description
Input
The first line contains an integer T (0 < T <= 10) means the number of the test cases.. For each test case: the first line contains two integers n and m, n is the number of the cities and m is the number of the roads (0 < n <= 10000, 0 < m < 100000). The following m lines describing the roads. Every line has three integers a, b, c (0 <= a, b < n, 0 < c < 100000), and one real number p (0.00001 < p < 1.00000), which means city a and city b is connected by a road whose length is c and probability to be occupied is p. The sum of all the p equals to 1.0.
Output
For each test case, output a line which contains a single real number x, the expected distance you will walk. You should accurate x to 0.001.
Sample Input
```1
3 3
0 1 1 0.5
0 2 1 0.25
2 1 1 0.25
```
Sample Output
`1.500`
Hint
In the sample test case: If the road (0, 1, 1) is occupied, the length of the shortest path is 2 and the probability is 0.5; If the road (0, 2, 1) is occupied, the length of the shortest path is 1 and the probability is 0.25; If the road (2, 1, 1) is occupied, the length of the shortest path is 1 and the probability is 0.25. So the expected distance you will walk is 2*0.5 + 1*0.25 + 1*0.25 = 1.500.
Source