2445 - DS_2021_Quiz4 Scoreboard

Time

2021/12/08 18:30:00 2021/12/08 20:00:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
13388 DS_2021_Quiz4_Graph

13388 - DS_2021_Quiz4_Graph   

Description

You are given a graph with n nodes, 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

(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;

Sample Input  Download

Sample Output  Download

Tags




Discuss