add 1514

fishercoder1534 · fishercoder1534 · commit 9dd58ac8b80b · 2020-07-12T06:32:33.000-07:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1514|[Path with Maximum Probability](https://leetcode.com/problems/path-with-maximum-probability/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1514.java) | |Medium|Graph|
 |1512|[Number of Good Pairs](https://leetcode.com/problems/number-of-good-pairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1512.java) | |Easy|Array, HashTable, Math|
 |1508|[Range Sum of Sorted Subarray Sums](https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1508.java) | |Medium|Array, Sort|
 |1507|[Reformat Date](https://leetcode.com/problems/reformat-date/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1507.java) | |Easy|String|
diff --git a/src/main/java/com/fishercoder/solutions/_1514.java b/src/main/java/com/fishercoder/solutions/_1514.java
@@ -0,0 +1,54 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Queue;
+
+public class _1514 {
+    public static class Solution1 {
+        public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
+            List<Integer>[] nodeToNodesList = new List[n];
+            List<Double>[] nodeToProbabilitiesList = new List[n];
+            for (int i = 0; i < n; i++) {
+                nodeToNodesList[i] = new ArrayList<>();
+                nodeToProbabilitiesList[i] = new ArrayList<>();
+            }
+            for (int i = 0; i < edges.length; i++) {
+                int u = edges[i][0];
+                int v = edges[i][1];
+                double w = succProb[i];
+                nodeToNodesList[u].add(v);
+                nodeToProbabilitiesList[u].add(w);
+
+                nodeToNodesList[v].add(u);
+                nodeToProbabilitiesList[v].add(w);
+            }
+
+            double[] probabilities = new double[n];
+            probabilities[start] = 1.0;
+            boolean[] visited = new boolean[n];
+            Queue<Integer> queue = new ArrayDeque<>();
+            queue.add(start);
+            visited[start] = true;
+            while (!queue.isEmpty()) {
+                int u = queue.poll();
+                visited[u] = false;
+
+                for (int i = 0; i < nodeToNodesList[u].size(); i++) {
+                    int v = nodeToNodesList[u].get(i);
+                    double w = nodeToProbabilitiesList[u].get(i);
+                    if (probabilities[u] * w > probabilities[v]) {
+                        probabilities[v] = probabilities[u] * w;
+                        if (!visited[v]) {
+                            visited[v] = true;
+                            queue.add(v);
+                        }
+                    }
+                }
+            }
+
+            return probabilities[end];
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1514Test.java b/src/test/java/com/fishercoder/_1514Test.java
