## Description

## Submission

class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> dp(n, 0); // max prob from start to node i
map<int, vector<pair<int, double>>> nextNodes;
for(int i = 0; i < edges.size(); ++i) {
nextNodes[edges[i][0]].push_back({edges[i][1], succProb[i]});
nextNodes[edges[i][1]].push_back({edges[i][0], succProb[i]});
}
queue<int> q;
dp[start] = 1;
q.push(start);
while(!q.empty()) {
int cur = q.front();
q.pop();
for(auto& nextNode: nextNodes[cur]) {
int next = nextNode.first;
double nextVal = nextNode.second;
double newProb = nextVal * dp[cur];
if(newProb > dp[next]) {
dp[next] = newProb;
q.push(next);
}
}
}
return dp[end];
}
};