※ 引述《enmeitiryous (enmeitiryous)》之铭言：
: 题目:
: 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])
我是直接硬套dijkstra 用max heap加更新条件改成max prob
然后因为机率越走越小 所以如果中间跑到end node就可以直接return结果了
虽然有过了不过跑的好慢 然后看别人答案感觉应该先想一下的==
class Solution {
public:
using pdi = pair<double, int>;
double maxProbability(int n, vector<vector<int>>& edges, vector<double>&
succProb, int start_node, int end_node) {
unordered_map<int, unordered_map<int, double>> graph;
priority_queue<pdi> pq;
for(int i = 0; i <edges.size(); ++i){
int u = edges[i][0], v = edges[i][1];
graph[u][v] = succProb[i];
graph[v][u] = succProb[i];
}
for(int i = 0; i < n; ++i){
if(graph[start_node][i] != 0){
pq.push({graph[start_node][i], i});
}
}
while(!pq.empty()){
auto [p, v] = pq.top();
pq.pop();
if(v == end_node) return p;
for(auto& [k, prob] : graph[v]){
auto& adj = graph[start_node];
if(k != v && adj[k] < adj[v] * graph[v][k]){
adj[k] = adj[v] * graph[k][v];
pq.push({adj[k], k});
}
}
}
return graph[start_node][end_node];
}
};