引述《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];
}
};
```