PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Marginalman
Re: [閒聊] 每日leetcode
作者:
oin1104
(是oin的說)
2024-08-27 11:35:09
引述《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];
}
};
```
作者:
JIWP
(JIWP)
2024-08-27 11:36:00
姆咪我一開始沒用heap,記憶體爆掉,太苦了
作者:
oin1104
(是oin的說)
2024-08-27 11:38:00
你就是還沒送我模型才會忘記用heap 你有什麼用
作者:
JIWP
(JIWP)
2024-08-27 11:39:00
" target="_blank" rel="noreferrer noopener nofollow">
給你看蕾米的燈籠褲
作者:
oin1104
(是oin的說)
2024-08-27 11:40:00
謝謝可以讓他跟妹妹在一起嗎就在旁邊而已 我看到了兩個一起拍照
作者:
JIWP
(JIWP)
2024-08-27 11:41:00
" target="_blank" rel="noreferrer noopener nofollow">
作者:
oin1104
(是oin的說)
2024-08-27 11:41:00
幹 好漂亮 這家叫甚麼
作者:
JIWP
(JIWP)
2024-08-27 11:42:00
alter
作者:
oin1104
(是oin的說)
2024-08-27 11:45:00
推薦那個靈夢模型
作者:
JIWP
(JIWP)
2024-08-27 11:47:00
蛤?
繼續閱讀
[姆咪] 訂了明天的機票
l00011799z
[瓦特] 蛋糕姬一張
Haku1Koyor1
[閒聊] 難怪我爸是賴粉
Leaflock
Re: [閒聊] 4060的顯卡:0
mayolan
Re: [邊緣] 跟阿芬約棒球約會 好緊張
wu10200512
[取暖] 中午吃水餃還是牛肉麵
NekomataOkay
Re: [閒聊] 還是其實我的品味很爛
cities516
→ ILoverika : 誤會 我不是甲
babagorou
[姆咪] 別的部門的主管
jjf0323
Re: [閒聊] 家人們 幫忙看一下我的品味
Leaflock
Links
booklink
Contact Us: admin [ a t ] ucptt.com