Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

引述《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: 姆咪
→ JIWP: 我一開始沒用heap，記憶體爆掉，太苦了
→ oin1104: 你就是還沒送我模型才會忘記用heap 你有什麼用
推 JIWP: http://i.imgur.com/49KDDNY.jpg
→ JIWP: 給你看蕾米的燈籠褲
→ oin1104: 謝謝
→ oin1104: 可以讓他跟妹妹在一起嗎
→ oin1104: 就在旁邊而已 我看到了
→ oin1104: 兩個一起拍照
→ JIWP: http://i.imgur.com/g1FFacY.jpg
→ oin1104: 幹 好漂亮 這家叫甚麼
→ JIWP: alter
→ oin1104: 推薦那個靈夢模型
推 JIWP: 蛤？