The expected distance
Time Limit : 3 Second
Memory Limit : 128 MB
Submission: 58
Solved: 3
- Description
- In the Mars, n cities are connected by a network of m bidirectional roads. It is known that these roads do not cross outside the cities. The label of the cities and the roads starts from 0. There is at most one road between two cities.
You are a postman, and now you have a very important mail to post from city 0 to city 1. However, the terrorist is in activity and they will occupy one road randomly, and every road has a probability to be occupied by the terrorist. If one road was occupied, you must select a shortest path without using that road. You can be sure that no matter which road is occupied, you always can find a path from city 0 to city 1 without using the occupied road.
Now give you all the probability of each road to be occupied, you must calculate the expected distance you will walk considering all the probability.
- 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