算法

(Dijkstra) $O((n + m)*log(n))$

使用Dijkstra求最短路，区别是把距离的相加改成相乘。

C++ 代码

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end)     {
        vector<vector<pair<int, double>>> G(n);
        for(int i = 0; i < (int)edges.size(); i += 1){
            auto u = edges[i];
            double w = succProb[i];
            if(w != 0.0){
                w = -log(w);
                G[u[0]].push_back({u[1], w});
                G[u[1]].push_back({u[0], w});
            }
        }
        vector<double> d(n, 1e10);
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
        vector<int> done(n);
        q.push({d[start] = 0, start});
        while(not q.empty()){
            auto u = q.top().second;
            q.pop();
            if(done[u]) continue;
            done[u] = 1;
            for(auto [v, w] : G[u])
                if(d[v] > d[u] + w)
                    q.push({d[v] = d[u] + w, v});
        }
        if(not done[end]) return 0;
        return exp(-d[end]);
    }
};

Python 代码

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        maps = defaultdict(list)
        for i in range(len(edges)):
            maps[edges[i][0]].append((edges[i][1], succProb[i]))
            maps[edges[i][1]].append((edges[i][0], succProb[i]))
        q = [(-1, start)]
        dist = defaultdict(float)
        dist[start] = -1
        while q:
            curdist, cur = heapq.heappop(q)
            if cur == end:
                return -curdist
            for node, prob in maps[cur]:
                tmp = curdist * prob
                if tmp < dist[node]:
                    dist[node] = tmp
                    heapq.heappush(q, (tmp, node))
        return 0