743.网络延迟时间 | 1514.概率最大的路径（Dijkstra算法）

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

思路：BFS+优先队列+贪心

[Python] BFS和DFS算法（第3讲）—— 从BFS到Dijkstra算法_哔哩哔哩_bilibili

Dijkstra 算法模板及应用 :: labuladong的算法小抄 (gitee.io)

求最短路径，所以优先队列用小根堆

初始化distance数组，距离都置为最大值 

class Solution {
public:
    int networkDelayTime(vectorint>>& times, int n, int k) 
    {
        vectorint,int>>> graph(n+1); 
        vector<int> distance(n+1,INT_MAX);//distance[i]表示k到i的最短距离
        vector<int> visited(n+1,0);//当i从优先队列中弹出时，visited[i]=1
        for(vector<int>& edge:times)//构建邻接表
        {
            int from=edge[0];
            int to=edge[1];
            int weight=edge[2];
            graph[from].emplace_back(to,weight);
        }
        //优先队列中存pair类型时，默认以pair.first排序，此处构建优先队列，默认以k到v的距离排序
        priority_queueint,int>,vectorint,int>>,greaterint,int>>> q;//小根堆
        q.emplace(0,k);//压入源节点k，距离为0
        while(!q.empty())
        {
            pair<int,int> min=q.top();//出一个队列中距离最近的
            q.pop();
            int dist=min.first;
            int v=min.second;
            //当前的k到v的距离，比k到v的最短距离大，则不进行下面的操作，再次进入循环，弹出队列中剩余的元素
            if(distance[v]
                continue;
            distance[v]=dist;//k到v的最短距离
            visited[v]=1;//已经得到了k距v的最短距离，所以记visited[i]=1
            for(pair<int,int> node:graph[v])//遍历与v相邻的其他结点
            {
                int to=node.first;
                int weight=node.second;
                if(!visited[to])//还没有找出k到to的最短路径
                {
                    //k到v的距离dist + v到to的距离weight 比当前的k到to的最短距离还小，就更新 
                    if(distance[to]>weight+dist)
                    {
                        q.emplace(weight+dist,to);
                        distance[to]=weight+dist;
                    }
                }
            }
        }
        int maxDistance=INT_MIN;
        for(int i=1;isize();i++)//遍历distance数组
        { 
            maxDistance=max(maxDistance,distance[i]);//找到k到所有结点的最短距离中最大的那个，即传递时间
            if(distance[i]==INT_MAX)//如果还存在INT_MAX,代表k无法到达该结点，返回-1
                return -1;
        }
        return maxDistance;
    }
};

 

1514.概率最大的路径 

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25

示例 2：

输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径

思路：迪杰斯特拉算法（bfs+贪心+优先队列）

因为要求概率最大的路径，所以优先队列是大根堆 

初始化distance数组，概率都置为0

class Solution {
public:
    double maxProbability(int n, vectorint>>& edges, vector<double>& succProb, int start, int end) {
        vector<int> visited(n,0);
        vector<double> distance(n,0);//初始化起点到所有结点的概率为0
        vectorint,double>>> graph(n);
        for(int i=0;isize();i++)//构建无向图的邻接表
        {
            int from=edges[i][0];
            int to=edges[i][1];
            double weight=succProb[i];
            graph[from].emplace_back(to,weight);
            graph[to].emplace_back(from,weight);
        }
        //大根堆，每次出概率最大的那个
        priority_queuedouble,int>,vectordouble,int>>,lessdouble,int>>> q;
        q.emplace(1,start);//压入起点，起点到起点概率为1
        while(!q.empty())
        {
            pair<double,int> out=q.top();
            q.pop();
            int v=out.second;
            double p=out.first;
            if(distance[v]>p)//如果最大概率比p大，就不用执行下面的代码
            {
                continue;
            }
            distance[v]=p;
            visited[v]=1;//已经得出起点到它的最大概率，visited[v]置为1
            for(pair<int,double> node:graph[v])//遍历v的相邻节点
            {
                int to=node.first;
                double weight=node.second;
                if(!visited[to])//没有得出起点到它的最大概率
                {
                    if(distance[to]//最大概率比p*weight小，就更新最大概率
                    {
                        distance[to]=p*weight;
                        q.emplace(p*weight,to);
                    }
                }
            }
        }
        return distance[end];
    }
};