首页 > 试题广场 >

分布式集群消息传递

[编程题]分布式集群消息传递
  • 热度指数：1024 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
有一个分布式服务集群，集群内含有 N 个服务节点，分别标记为 1 到 N。
给予一个列表 times，表示消息从两个节点间有向传递需要的时间。 times[i] = (s, d, t)，其中 s 表示发出消息的源节点，d 表示接收到消息的目标节点， t  表示信息有向传递的时间。
现在 K 节点发送了一个信号，请问至少需要多少秒才能使所有的服务节点都收到该消息？如果消息不能传递给集群内全部节点，则返回-1。

输入描述:
第一行：列表 times。分布式服务集群的图，图的结构为二维数组。例如： [[2,1,1],[2,3,1],[3,4,1]] ，表示集群4个节点，2到1的时间为1，2到3的时间为1，3到4的时间为1；
第二行：N值
第三行：K值
范围约束：
1. N 的范围在 [1, 100] 之间。
2. K 的范围在 [1, N] 之间。
3. times 的长度在 [1, 6000] 之间。
4. 所有的边 times[i] = (s, d, t) 都有 1 <= s, d <= N 且 1 <= t <= 100。


输出描述:
至少需要多少秒才能使所有的服务节点都收到该消息？如果消息不能传递给集群内全部节点，则返回-1
示例1

输入

[[2,1,1],[2,3,1],[3,4,1]]
4
2

输出

2

备注:
图可能存在重边或自环
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

运维工程师 小米集团 图 2019
来自：小米2019秋招运维工...
上传者：小小
难度：
0条回答 5012浏览

热门推荐

通过挑战的用户

查看代码

相关试题

分布式集群消息传递

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号