Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Path With Maximum Probability

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
Techwave ConsultingMAQ Software

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, Images )
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
1
4 2 0 2
0 1
2 3
0.8 0.8
Sample Output 2
0.000000
Full screen
Console