New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Path With Maximum Probability

Contributed by

Vivek Kumar Mehta

Medium

0/80

Avg time to solve 25 mins

Success Rate 75 %

2 upvotes

Problem Statement

You are given an undirected unweighted graph and an array 'sProability' which denotes the probability of traversing edges such that 'sProability[i]' denotes the probability of traversing ith edge. You are given the start and end vertex, You need to determine the maximum path probability on going from start to end vertex if there is no path from start to end return 0.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format

The first line of input contains an integer 'T', the number 
of test cases.

The first line of the test case contains four integers ‘N’, 
‘M’, 'START', 'END' denoting the number of vertices, edges, starting vertex, and ending vertex.

The next ‘M’ lines describe the edge. Each edge is 
characterized by two integers ‘A’ and ‘B’ where ‘A’ and ‘B’ denotes the endpoints of the edge.

The last line of each test case contains ‘M’ space-separated floating-point number denoting the probability of traversing ith edge.

The edges[i][0], edges[i][1] contains the vertex that is 
connected to the edge.

Output Format

Return the maximum probability of path from start to end vertex up to 6 decimal places. If there is no path, return 0.

Note:

Graph does not contain self-loops.

Constraints

1 <= T <= 10
1 <= N <= 5 * 10 ^ 4
1 <= M <= min((N * (N - 1) / 2),10^5)
0 <= VERTEX VALUE, START, END <= N - 1
0 <= sProability[i] <= 1

Time Limit: 1 second

Sample Input 1

1
3 3 0 2
0 1
1 2
0 2
0.9 0.9 0.75

Sample Output 1

0.810000

Explanation for Sample Output 1:

For the test case 1:

The graph is as follows:

Path with maximum probability from 0 to 1 is 0->2->1. Hence the maximum probability is 0.90 * 0.90 = 0.81.

Sample Input 2

Sample Output 2

0.000000

Auto

Console