# | Problem | Pass Rate (passed user / total user) |
---|---|---|
13388 | DS_2021_Quiz4_Graph |
|
Description
You are given a graph with n nodes, m edges.
Each edge has three numbers a, b, p, representing an undirected weight edge connecting the nodes a and b with a probability p (success rate) traversing through that edge.
There are r queries.
Each query gives two nodes S and E, you are asked to find the path with the maximum success rate to go from S to E and print its success probability.
Input
Top three lines of input: n m r
The following m lines represented undirected weighted edges:
a b p
Then followed by r queries: S E
Note:
n (number of nodes): 0 < n <= 500, node’s ID starts from 0
m (number of edges): 0 < m <= 2000
r (number of query): 0 < r <= 100
p (probability of success): double, 0.0 <= p <=1.0
Output
1. For each query, print the maximum probability of success to go from S to E.
2. Print the probability to the fifth digit after the decimal point.
3. If the probability has more than five digits after the decimal point, round down (無條件捨去) to the fifth digit.
4. If there is no path from S to E, print 0.00000. If S == E, print 1.00000.
5. Each line ends with a newline character.
6. You can use the following code to control your output:
#include<iomanip>
cout<<fixed<< setprecision(5)<<probability<<endl;