Longest Path Solution
Leetcode #1514unknown
c_cpp
a month ago
1.3 kB
4
Indexable
class Solution { public: double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int src, int dst) { unordered_map<int, vector<pair<double, int>>> graph; for (int i = 0; i < edges.size(); i++) { int u = edges[i][0], v = edges[i][1]; double dist = succProb[i]; if (!graph.count(u)) { graph[u] = {}; } if (!graph.count(v)) { graph[v] = {}; } graph[u].push_back({dist, v}); graph[v].push_back({dist, u}); } priority_queue<pair<double, int>> pq; pq.push({1, src}); bool finalAns = 0; vector<double> distances(n, 0); while (!pq.empty()) { auto [currProb, currNode] = pq.top(); pq.pop(); for (auto [weight, child]: graph[currNode]) { double newDist = currProb * weight; if (newDist > distances[child]) { pq.push({newDist, child}); distances[child] = newDist; } } } return distances[dst]; } };
Editor is loading...
Leave a Comment