Re: [閒聊] 每日leetcode

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/08/27 11:35)推噓3(3推 0噓 11→)

留言14則, 2人參與討論串770/1549 (看更多)

引述《enmeitiryous (enmeitiryous)》題目: 1514. Path with Maximum Probability 給你一個圖有n個點，並給你一個vector:edge，每一個edge(u,v)的weight是從 u到v的成功機率(0<=w<=1)，給定起始點s和終點d，求s到d的成功率最大路徑思路: 因為是無向圖比較姆咪一點我用Dijkstra's 每次都往四周看然後把可以走的地方丟到pq裡面這次有記得用priority queue 了丟進去一直邊走邊看就可以了姆咪 ```cpp class Solution { public: double maxProbability(int n, vector<vector<int>>& edges, vector<double>& suc cProb, int start_node, int end_node) { vector<vector<pair<int,double>>> path(n); vector<double> paper(n,0); int len = edges.size(); for(int i = 0 ; i < len ; i ++) { path[edges[i][1]].push_back({edges[i][0] , succProb[i]}); path[edges[i][0]].push_back({edges[i][1] , succProb[i]}); } priority_queue<pair<double,int>> pq; pq.push({1,start_node}); while(!pq.empty()) { int dest = pq.top().second; double prob = pq.top().first; pq.pop(); if(paper[dest] >= prob)continue; if(dest == end_node)return prob; paper[dest] = prob; for(auto k : path[dest]) { int next = k.first; double nextprob = k.second; pq.push({prob*nextprob , next}); } } return paper[end_node]; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.18.201 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724729711.A.C9A.html

推

JIWP

08/27 11:36, 1年前 , 1^F

08/27 11:36, 1^F

→

JIWP

08/27 11:37, 1年前 , 2^F

08/27 11:37, 2^F

→

oin1104

08/27 11:38, 1年前 , 3^F

08/27 11:38, 3^F