推 DJYOMIYAHINA: 放過我 08/27 10:44
推 sustainer123: diijkstra好難 08/27 10:52
→ enmeitiryous: 我覺得geek的diijkstra 講的還不錯欸 我也是早上看 08/27 10:55
→ enmeitiryous: 那個學怎麼寫的 08/27 10:56
題目:
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