任意着色顶点的最大距离和非着色顶点的最大距离
任意着色顶点的最大距离和非着色顶点的最大距离
提问于 2022-03-03 17:11:20
问题
城市中有n个位置(顶点)，它们通过长度为1(边长=1)的街道相连。有些地方有加油站(彩色顶点)，而另一些则没有。在没有加油站的地方，人们去他们最近的加油站。找到加油站可能要走的最长距离是多少？
我的解决方案
我已经想出了一个BFS方法，我将非汽油位置的最大距离初始化为max_int，然后从每个汽油位置进行BFS，并不断更新非汽油位置的距离。然而，我觉得这个问题必须有一个更好的解决办法。
回答 1
Stack Overflow用户
发布于 2022-03-03 20:30:45
LOOP N over uncolored vertices
SET D(N) = MAX INT
LOOP N over uncolored vertices
BFS from N DO FOR each V reached
IF V is colored
STOP BFS ( no need to search further )
ELSE IF N-V distance less than D(N)
D(V) = N-V distance
SET M = 0
LOOP N over uncolored vertices
IF D(N) > M
M = D(N)
OUTPUT M页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71341058
复制相关文章
相似问题
腾讯云开发者
