引述《enmeitiryous (enmeitiryous)》
题目:
1514. Path with Maximum Probability
给你一个图有n个点，并给你一个vector:edge，每一个edge(u,v)的weight是从
u到v的成功机率(0<=w<=1)，给定起始点s和终点d，求s到d的成功率最大路径
思路:
因为是无向图
比较姆咪一点
我用Dijkstra's
每次都往四周看
然后把可以走的地方丢到pq里面
这次有记得用priority queue 了
丢进去一直边走边看就可以了
姆咪
```cpp
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& suc
cProb, int start_node, int end_node)
{
vector<vector<pair<int,double>>> path(n);
vector<double> paper(n,0);
int len = edges.size();
for(int i = 0 ; i < len ; i ++)
{
path[edges[i][1]].push_back({edges[i][0] , succProb[i]});
path[edges[i][0]].push_back({edges[i][1] , succProb[i]});
}
priority_queue<pair<double,int>> pq;
pq.push({1,start_node});
while(!pq.empty())
{
int dest = pq.top().second;
double prob = pq.top().first;
pq.pop();
if(paper[dest] >= prob)continue;
if(dest == end_node)return prob;
paper[dest] = prob;
for(auto k : path[dest])
{
int next = k.first;
double nextprob = k.second;
pq.push({prob*nextprob , next});
}
}
return paper[end_node];
}
};
```