LeetCode 743. Network Delay Time
原题链接在这里:https://leetcode.com/problems/network-delay-time/
题目:
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
.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
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 have1 <= u, v <= N
and0 <= w <= 100
.
题解:
Construct a graph. Then use the shortest time to traverse to the point.
Have a minHeap based on the time spent to get to the point. With the graph and current point, find all the next points and calculate the time to get to that point, current.time + time from current to next point, put it to minHeap.
Thus, we could always get to a point with shortest time.
Note: Update visited set when poll out of minHeap but not before adding to the heap. Otherwise, if it takes very long time to next point and add the next point to visited, later if there is shorter path to that point, it can't be added to minHeap.
So update visited set after polling out of minHeap and update res if it is not visited before.
Time Complexity: O(E+VlogV). It takes O(E) time to construct graph. O(VlogV) time to traverse all the points.
Space: O(E+V). O(E) for graph, O(V) for minHeap and Set.
AC Java:
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int []>> graph = new HashMap<>();
for(int [] edge : times){
graph.putIfAbsent(edge[0], new ArrayList<int []>());
graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
} int res = 0; PriorityQueue<int []> minHeap = new PriorityQueue<int []>((a,b) -> a[0]-b[0]);
minHeap.add(new int[]{0, K});
Set<Integer> visited = new HashSet<Integer>();
int count = 0; while(!minHeap.isEmpty()){
int[] cur = minHeap.poll();
if(visited.contains(cur[1])){
continue;
} visited.add(cur[1]);
count++;
res = cur[0];
if(graph.containsKey(cur[1])){
for(int [] next : graph.get(cur[1])){
minHeap.add(new int[]{res+next[1], next[0]});
}
}
} return count == N ? res : -1;
}
}
最新文章
- c#+handle.exe实现升级程序在运行时自动解除文件被占用的问题
- net cookie操作
- django中添加用户
- php curl 中的gzip压缩性能测试
- The Java™ Tutorials下载地址
- Android中文API(129) —— AudioManager
- U31网管配置
- 树莓派播放视频的播放器omxplayer
- 开启SSH
- 26 python 初学(线程、同步锁、死锁和递归锁)
- BZOJ3498PA2009 Cakes——三元环
- php之常用扩展总结
- 数据结构 Sunday算法
- 剑指offer(48)不用加减乘除做加法
- AWS EC2 使用root账户密码登陆
- Sql 中存储过程详细案例
- MySQL从删库到跑路(六)——SQL插入、更新、删除操作
- 4 python内置函数
- 美团外卖Android平台化的复用实践
- 触发器三(行级DML触发器)(学习笔记)