[leetcode] 743. Network Delay Time

[leetcode] 743. Network Delay Time

Description

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

N will be in the range [1, 100].K will be in the range [1, N].The length of times will be in the range [1, 6000].All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

分析

题目的意思是：给你很多三元组作为无向图的边，u是起始节点，v是终止节点，然后w是时间，现在从K发射一个信号，问所有的节点接收到这个信号需要耗费多长时间，如果不可能到达，就返回-1.

当有对边 (u, v) 是结点u到结点v，如果 dist(v) > dist(u) + w(u, v)，那么 dist(v) 就可以被更新，这是所有这些的算法的核心操作。Dijkstra算法是以起点为中心，向外层层扩展，直到扩展到终点为止。为了防止重复比较，我们需要使用visited数组来记录已访问过的结点，最后我们在所有的最小路径中选最大的返回（如果最长的路径上的节点都能到达，那其他路径的节点就能到达），注意，如果结果res为INT_MAX，说明有些结点是无法到达的，返回-1。普通的实现方法的时间复杂度为O(V2)，基于优先队列的实现方法的时间复杂度为O(E + VlogV)，其中V和E分别为结点和边的个数.

代码

class Solution {public: int networkDelayTime(vector>& times, int N, int K) { int res=0; vector> edges(101,vector(101,-1)); queue q{{K}}; vector dist(N+1,INT_MAX); dist[K]=0; for(auto e:times){ edges[e[0]][e[1]]=e[2]; } while(!q.empty()){ unordered_set visited; for(int i=q.size();i>0;i--){ int u=q.front(); q.pop(); for(int v=1;v<=100;v++){ if(edges[u][v]!=-1&&dist[u]+edges[u][v]

参考文献

​​[LeetCode] Network Delay Time 网络延迟时间​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。