pastaPicasoToday's problem is standard problem of BFS,
But it can teach us some c++ concepts such as using priority_queue correctly.
For this specific solution i have made a custom element and overwritten the less-than operator for it.
this makes me go thru the graph in order of probablity.
higher probability region will be explored first.
and this solution is accepted.
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<int,double>>> adj(n);
int cnt = 0;
for(auto i : edges) {
adj[i[0]].push_back({i[1], succProb[cnt]});
adj[i[1]].push_back({i[0], succProb[cnt]});
cnt++;
}
struct elem {
double prob;
int point;
bool operator < (const struct elem &a) const {
return this->prob < a.prob;
}
};
/* will pick up higher probabilities first */
vector<double> probs(n,0.);
probs[start] = 1.;
priority_queue<elem> pq;
pq.push(elem{1., start});
while(!pq.empty()) {
elem t = pq.top();
pq.pop();
cout << t.point << endl;
if (t.point == end) {
break;
}
for(auto i : adj[t.point]) {
// probs[i.first] = max(probs[i.first],
// probs[t.point] * i.second);
// pq.push(elem{probs[i.first],i.first}); // we just push the point, and we dont care about the prob.
if (probs[i.first] < probs[t.point] * i.second) {
probs[i.first] = probs[t.point] * i.second;
pq.push(elem{probs[i.first], i.first});
}
}
}
return probs[end];
}
};
But seems like there are more complicated and FAST solutions for this problem.
For example using this Graph-DP.
which has half the runtime.
