| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13025 | DS_2020_QUIZ4_Graph |
|
Description
You are given an undirected weighted graph of n nodes, represented by an edge list where a triplet a, b, p represents an undirected edge connecting the nodes a and b with a probability p of success of traversing that edge.
Given two nodes start and end, you are asked to find the path with the maximum probability of success to go from start to end and print its success probability.
If there is no path from start to end, return 0.00000.
Input
1. First line of input: n (number of nodes)
2. Second line of input: m (number of edges)
3. Third line of input: r (number of instructions of finding path), 0<r<=100
4. Then followed by m lines of undirected weighted graph’s edges: a b p
5. Then followed by r lines of instruction of the start and end nodes: start end
Note:
n (number of nodes): Integer, 0<n<=100
node’s ID starts from 0
m (number of edges): Integer, 0<m<=C(n,2)
r (number of instructions of finding path): Integer, 0<r<=100
p (probability of success to go from a to b): float, 0.0<p<=1.0
Output
1. For instructions of finding the path, print the maximum probability of success to go from start to end.
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 start to end, print 0.00000. Each line ends with a newline character.
5. You can use the following code to control your output:
#include<iomanip>
cout<<fixed<< setprecision(5)<<probability<<endl;