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