1
class Pair {
2
  int to;
3
  double prob;
4

5
  public Pair(int to, double prob) {
6
    this.to = to;
7
    this.prob = prob;
8
  }
9
}
10

11
class Solution {
12
  public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
13
    List<List<Pair>> adj = new ArrayList<>();
14
    for (int i = 0; i < n; i++) {
15
      adj.add(new ArrayList<Pair>());
16
    }
17
    for (int i = 0; i < edges.length; i++) {
18
      adj.get(edges[i][0]).add(new Pair(edges[i][1], succProb[i]));
19
      adj.get(edges[i][1]).add(new Pair(edges[i][0], succProb[i]));
20
    }
21
    // node,to node,probability
22
    double probs[] = new double[n];
23
    Arrays.fill(probs, 0.0);
24
    probs[start] = 1.0;
25
    PriorityQueue<Pair> pq = new PriorityQueue<>((p1, p2) -> Double.compare(p2.prob, p1.prob));
26
    pq.offer(new Pair(start, 1.0));
27
    while (!pq.isEmpty()) {
28
      Pair curr = pq.poll();
29
      for (Pair x : adj.get(curr.to)) {
30
        if (((curr.prob) * (x.prob)) > probs[x.to]) {
31
          probs[x.to] = ((curr.prob) * (x.prob));
32
          pq.offer(new Pair(x.to, probs[x.to]));
33

34
        } else {
35
          continue;
36
        }
37
      }
38
    }
39
    return probs[end];
40
  }
41
}