leetcode

0 class Solution {

1 typedef tuple<double, int> edge;

2

3 public:

4 double maxProbability(int n, const vector<vector<int>> &edges, const vector<double> &succProb, int start,

5 int end) {

6 vector<vector<edge>> adj(n);

7 vector<bool> visited(n, false);

8 vector<double> dist(n, 0);

9 priority_queue<edge> pq;

10

11 for (int i = 0; i < succProb.size(); i++) {

12 adj[edges[i][0]].push_back({succProb[i], edges[i][1]});

13 adj[edges[i][1]].push_back({succProb[i], edges[i][0]});

14 }

15

16 pq.push({dist[start] = 1.0, start});

17 while (n && !pq.empty()) {

18 auto [w, dest] = pq.top();

19 pq.pop();

20 if (visited[dest]) continue;

21 if (dest == end) return w;

22 visited[dest] = true;

23 for (const auto &[pw, pd] : adj[dest]) {

24 if (!visited[pd] && dist[dest] * pw > dist[pd]) {

25 dist[pd] = dist[dest] * pw;

26 pq.push({dist[pd], pd});

27 }

28 }

29 n--;

30 }

31

32 return 0;

33 }

34 };