leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1514.cpp (1111B)

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 };