leetcode1514. 概率最大的路径

朴素Dijsktra

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<double>>g(n,vector<double>(n,0.0));
        for(int i=0;i<succProb.size();i++){
            int a=edges[i][0], b=edges[i][1];
            double c=succProb[i];
            g[a][b]=c;
            g[b][a]=c;
        }
        vector<double>dist(n,0.0);//距离初始为0，表示不可达
        vector<bool>used(n,false);
        dist[start]=1.0;//起点概率最大
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=0;j<n;j++){
                if(!used[j]&&(t==-1||dist[j]>dist[t]))t=j;
            }
            used[t]=true;
            for(int j=0;j<n;j++)
                dist[j]=max(dist[j],dist[t]*g[t][j]);
        }
        return dist[end];
    }
};

优化版Dijsktra

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<edges.size();i++){
            g[edges[i][0]].push_back({edges[i][1],succProb[i]});
            g[edges[i][1]].push_back({edges[i][0],succProb[i]});
        }
        vector<double>dist(n,0.0);//距离初始为0，表示不可达
        vector<bool>used(n,false);
        dist[start]=1.0;//起点概率最大
        priority_queue<pair<double,int>>q;//大根堆
        q.push({1.0,start});
        while(!q.empty()){
            auto [p,ver]=q.top();//当前概率最大的顶点
            q.pop();
            if(used[ver])continue;
            used[ver]=true;
            for(auto [v,w]:g[ver]){//找到ver的邻接点，更新概率
                if(dist[v]<w*dist[ver]){
                    dist[v]=w*dist[ver];
                    q.push({dist[v],v});
                }
            }
        }
        return dist[end];
    }
};