1
class Solution {
2
 public:
3
  double maxProbability(int n, vector<vector<int>> &edges, vector<double> &succProb, int start,
4
                        int end) {
5
    vector<vector<pair<int, double>>> graph(n);
6
    for (int i = 0; i < edges.size(); ++i) {
7
      graph[edges[i][0]].push_back({edges[i][1], succProb[i]});
8
      graph[edges[i][1]].push_back({edges[i][0], succProb[i]});
9
    }
10
    priority_queue<pair<double, int>> pq;
11
    pq.push({1.0, start});
12
    vector<bool> visited(n, false);
13
    vector<double> values(n, 0.0);
14
    values[start] = 1.0;
15
    while (!pq.empty()) {
16
      double currValue = pq.top().first, currNode = pq.top().second;
17
      pq.pop();
18
      visited[currNode] = true;
19
      for (int i = 0; i < graph[currNode].size(); ++i) {
20
        double weight = graph[currNode][i].second;
21
        int nextNode = graph[currNode][i].first;
22
        if (visited[nextNode] == false) {
23
          double nextProb = currValue * weight;
24
          if (nextProb > values[nextNode]) values[nextNode] = nextProb;
25
          pq.push({nextProb, nextNode});
26
        }
27
      }
28
    }
29
    return values[end] == 0.0 ? 0.0 : values[end];
30
  }
31
};