题目:
1514. Path with Maximum Probability
给你一个图有n个点，并给你一个vector:edge，每一个edge(u,v)的weight是从
u到v的成功机率(0<=w<=1)，给定起始点s和终点d，求s到d的成功率最大路径
思路:
我们可以先将每个edge的weight转换成-log的格式，所求就等价于求s to d的最短
路径，可以用diijkstra求即可，回传要取-exp(dist[d])
double maxProbability(int n, vector<vector<int>>& edges, vector<double>&
succProb, int start_node, int end_node) {
for(int i=0;i<succProb.size();++i){
succProb[i]=-log(succProb[i]);
}
priority_queue<pair<double,double>,vector<pair<double,double>>,greater<pair<double,double>>>
pq;
vector<vector<pair<double,double>>>
grap(n,vector<pair<double,double>>());
for(int i=0;i<edges.size();++i){
grap[edges[i][0]].push_back(make_pair(succProb[i],edges[i][1]));
grap[edges[i][1]].push_back(make_pair(succProb[i],edges[i][0]));
}
vector<double> disc(n,10001);
disc[start_node]=0;
pq.push(make_pair(0,start_node));
while(!pq.empty()){
int ne_xt=(int)pq.top().second;
pq.pop();
for(auto &neigh:grap[ne_xt]){
if(disc[neigh.second]>disc[ne_xt]+neigh.first){
disc[neigh.second]=disc[ne_xt]+neigh.first;
pq.push(make_pair(disc[neigh.second],neigh.second));
}
}
}
return exp(-disc[end_node]);
}