1514. Path with Maximum Probability Medium

1/**
2 * [1514] Path with Maximum Probability
3 *
4 * You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
5 * Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
6 * If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex1.png" style="width: 187px; height: 186px;" />
10 * 
11 * Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
12 * Output: 0.25000
13 * Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex2.png" style="width: 189px; height: 186px;" />
17 * 
18 * Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
19 * Output: 0.30000
20 * 
21 * Example 3:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex3.png" style="width: 215px; height: 191px;" />
23 * 
24 * Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
25 * Output: 0.00000
26 * Explanation: There is no path between 0 and 2.
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	2 <= n <= 10^4
32 * 	0 <= start, end < n
33 * 	start != end
34 * 	0 <= a, b < n
35 * 	a != b
36 * 	0 <= succProb.length == edges.length <= 2*10^4
37 * 	0 <= succProb[i] <= 1
38 * 	There is at most one edge between every two nodes.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/path-with-maximum-probability/
44// discuss: https://leetcode.com/problems/path-with-maximum-probability/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn max_probability(n: i32, edges: Vec<Vec<i32>>, succ_prob: Vec<f64>, start: i32, end: i32) -> f64 {
50        0f64
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_1514() {
62    }
63}
64