743. 网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
image.png
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
提示：
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）
经分析，此题的题意就是在有正权有向且可能存在环的图里从给定的点出发，直到到达所有点的最终权重和，如果不能到达所有点则返回-1。这也是要背诵的基础DFS算法，问一问AI即可。
# @return {Integer}
require 'algorithms'
def network_delay_time(times, n, k)
h = (1..n).to_h {|it| [it ,{}]}
times.each do |t|
h[t[0]][t[1]] = t[2]
end
m = dijkstra(h,k)
if m.length < n
return -1
else
return m.values.max
end
end
def dijkstra(graph, source)
dist = Hash.new(Float::INFINITY)
dist[source] = 0
pq = Containers::PriorityQueue.new
pq.push(source, 0)
until pq.empty?
u = pq.pop
graph[u].each do |v, weight|
if dist[v] > dist[u] + weight
dist[v] = dist[u] + weight
pq.push(v, -dist[v])
end
end
end
dist
end
