问最小RGB路径
EN

Stack Overflow用户

提问于 2020-01-18 19:00:46

回答 1查看 144关注 0票数 1

给出了有向图G = (V, E)加权边。节点颜色为红色、绿色和蓝色。如果包含红色、绿色和蓝色节点，则从的到v的路径称为多姿多彩。

找到s和每个v之间的最短路径，条件是路径应该是彩色的。如果有不止一条道路是丰富多彩的，找出两者之间的最小值。

如果没有这样的路径，则返回false。

我不知道该怎么开始。任何帮助都是非常感谢的！

发布于 2020-01-18 20:35:09

当您沿着从s到v的路径时，从一种“状态”走到另一种“状态”，其中“状态”既包括您所在的节点，也包括您在旅途中所处节点的颜色(7种可能的组合)。状态确定当前位置的哪些路径是有效的解决方案。

从原始图中，创建(或想象)一个可访问状态图，其中边表示从一种状态到另一种状态的转换能力。对于每个原始图顶点，这个图最多有7个顶点。

现在使用Dijkstra算法从(s，red) (假设s是红色)到(v，red+green+blue)的最短路径。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/59803864

复制

相似问题

问最小RGB路径EN