※ 引述《enmeitiryous (enmeitiryous)》之銘言： : 題目: : 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]) 我是直接硬套dijkstra 用max heap加更新條件改成max prob 然後因為機率越走越小 所以如果中間跑到end node就可以直接return結果了 雖然有過了不過跑的好慢 然後看別人答案感覺應該先想一下的== class Solution { public: using pdi = pair<double, int>; double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) { unordered_map<int, unordered_map<int, double>> graph; priority_queue<pdi> pq; for(int i = 0; i <edges.size(); ++i){ int u = edges[i][0], v = edges[i][1]; graph[u][v] = succProb[i]; graph[v][u] = succProb[i]; } for(int i = 0; i < n; ++i){ if(graph[start_node][i] != 0){ pq.push({graph[start_node][i], i}); } } while(!pq.empty()){ auto [p, v] = pq.top(); pq.pop(); if(v == end_node) return p; for(auto& [k, prob] : graph[v]){ auto& adj = graph[start_node]; if(k != v && adj[k] < adj[v] * graph[v][k]){ adj[k] = adj[v] * graph[k][v]; pq.push({adj[k], k}); } } } return graph[start_node][end_node]; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.34.222.80 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724728009.A.9F8.html