Re: [閒聊] 每日leetcode
※ 引述《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];
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.34.222.80 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724728009.A.9F8.html
推
08/27 11:30,
1年前
, 1F
08/27 11:30, 1F
推
08/27 22:41,
1年前
, 2F
08/27 22:41, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 769 之 1549 篇)：