Given 是一个无向的加权图。每个节点要么是一个“城市”，要么是一个“村庄”；节点通过边（=道路）连接。
我从节点 1 开始，必须向所有城市传达信息。在某人到达的每个城市中，任意数量的人都可以帮助传播信息（这样他们就可以开始开车到另一个节点）。
我现在正在寻找必须在道路上行驶的最小距离，以便所有城市都能收到信息。（当 x 人使用特定道路时，它也计算 x 倍边缘权重）
解决方案：我认为，首先在所有城市之间获得最小生成树会很有帮助。但问题是，也有村庄。（-->“施泰纳树问题”）。所以我想有可能用 Dijkstra 或 Bellman-Ford 以某种方式解决它；还是最短路径和MST的组合？
你们有什么想法吗？我不需要代码，但只是一个基本的想法如何解决这个问题会非常有帮助:) 谢谢。