1514.cpp (1111B)
1 class Solution { 2 typedef tuple<double, int> edge; 3 4 public: 5 double maxProbability(int n, const vector<vector<int>> &edges, const vector<double> &succProb, int start, 6 int end) { 7 vector<vector<edge>> adj(n); 8 vector<bool> visited(n, false); 9 vector<double> dist(n, 0); 10 priority_queue<edge> pq; 11 12 for (int i = 0; i < succProb.size(); i++) { 13 adj[edges[i][0]].push_back({succProb[i], edges[i][1]}); 14 adj[edges[i][1]].push_back({succProb[i], edges[i][0]}); 15 } 16 17 pq.push({dist[start] = 1.0, start}); 18 while (n && !pq.empty()) { 19 auto [w, dest] = pq.top(); 20 pq.pop(); 21 if (visited[dest]) continue; 22 if (dest == end) return w; 23 visited[dest] = true; 24 for (const auto &[pw, pd] : adj[dest]) { 25 if (!visited[pd] && dist[dest] * pw > dist[pd]) { 26 dist[pd] = dist[dest] * pw; 27 pq.push({dist[pd], pd}); 28 } 29 } 30 n--; 31 } 32 33 return 0; 34 } 35 };