首页 > 试题广场 >

分布式集群消息传递

[编程题]分布式集群消息传递
  • 热度指数：1023 时间限制：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

备注:
图可能存在重边或自环
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-28 16:53:08
解题思路 这是一个基于Dijkstra算法的最短路径问题： 将服务节点之间的消息传递时间构建为有向图 使用Dijkstra算法计算从起始节点 到所有其他节点的最短路径 找出所有最短路径中的最大值，即为所需的最小时间 如果存在无法到达的节点（距离为 ），则返回-1 关键点： 需要正确处理输入格 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

分布式集群消息传递

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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