Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/27 10:43)推噓2(2推 0噓 2→)留言4則, 3人參與討論串768/1548 (看更多)
題目:
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])
double maxProbability(int n, vector<vector<int>>& edges, vector<double>&
succProb, int start_node, int end_node) {
for(int i=0;i<succProb.size();++i){
succProb[i]=-log(succProb[i]);
}
priority_queue<pair<double,double>,vector<pair<double,double>>,greater<pair<double,double>>>
pq;
vector<vector<pair<double,double>>>
grap(n,vector<pair<double,double>>());
for(int i=0;i<edges.size();++i){
grap[edges[i][0]].push_back(make_pair(succProb[i],edges[i][1]));
grap[edges[i][1]].push_back(make_pair(succProb[i],edges[i][0]));
}
vector<double> disc(n,10001);
disc[start_node]=0;
pq.push(make_pair(0,start_node));
while(!pq.empty()){
int ne_xt=(int)pq.top().second;
pq.pop();
for(auto &neigh:grap[ne_xt]){
if(disc[neigh.second]>disc[ne_xt]+neigh.first){
disc[neigh.second]=disc[ne_xt]+neigh.first;
pq.push(make_pair(disc[neigh.second],neigh.second));
}
}
}
return exp(-disc[end_node]);
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.118.155.72 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724726610.A.DE3.html
推
08/27 10:44,
1年前
, 1F
08/27 10:44, 1F
推
08/27 10:52,
1年前
, 2F
08/27 10:52, 2F
→
08/27 10:55,
1年前
, 3F
08/27 10:55, 3F
→
08/27 10:56,
1年前
, 4F
08/27 10:56, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 768 之 1548 篇)：