这是数据结构和算法课程的一个问题，所以我不是在寻找一个具体或完整的答案，但希望能帮助我看看我是否走在正确的轨道上（或者那些可以指出我正确的提示）追踪）
给定一个位置的无向图，其中节点是位置，道路是边（加权通过某条道路所需的时间），找到可以以最大权重到达所有节点的最小点数* 5. *点是图表上的任何点。它们可以在边缘或节点上。从现在开始，我将它们称为临界点。
例如，如果我们有这个图表：
节点1->节点3（权重1）->节点2（权重7）
node2->node1(权重 7)->node4(w 1)->node7(w 8)
节点3->节点1(1)->节点4(2)->节点5(2)->节点6(2)
节点4->节点2(1)->节点3(2)->节点5(2)
节点5->节点3(2)->节点4(2)->节点7(3)
节点6->节点3(2)->节点7(5)
节点7->节点6(5)->节点5(3)->节点2(8)
那么关键点是：一个在节点 1 和 2 之间的边缘，节点 1 的权重为 2，节点 2 的权重为 5（注意它们的总和必须仍然等于 7，即节点 1 到 2 的原始权重)，第二个在节点 7 上。第一个临界点可以到达节点 1 到 6，最大权重为 5。只有节点 7 在权重 5 上无法到达，因此第二个临界点在节点 7 本身上。因此，从这两个权重为 5（或更少）的关键点可以到达整个图。
我的想法：为每个鼻子保留一个布尔“完成”，表明它可以或不能从已经找到的关键点之一到达。从某个节点开始。使用 BFS 并遍历图。在未完成的节点上，执行以下操作：
检查节点的邻接列表。忽略权重大于 10 的边，因为您无法放置到达您所在节点的临界点以及这些边所通向的节点。忽略通向“完成”节点的边。如果没有剩余边，则将与当前节点位置相同的临界点添加到临界点列表中。否则，检查剩余的最大权重边，并在该边上创建一个临界点：临界点的 2 个选项。从 curr_node 到 critical_point=5，从 critical_node 到相邻节点（边缘通向的节点）的权重是 edgeWeight-5，或者：从 crtical_point 到相邻节点的权重是 5，从 curr_node 到 critical_point 的权重是 edgeWeight-5。尝试两者并检查哪个关键点可以到达权重为 5 的更多节点。使用具有更多可到达节点的节点并将这些节点标记为已完成。
这里的问题是有效性证明。每个临界点有不止 2 个选项（当使用最大的权重边缘时），我只考虑 2 个。但另一方面，如果我考虑更多，我们会遇到复杂性问题，并且算法已经不是太优化。此外，我们可能需要在节点周围的边缘上放置多个临界点。该算法只放置一个或不放置并继续前进，因为我假设放置多个可能会放置比需要更多的点。
所以基本上，我不太确定从这里去哪里。任何帮助将不胜感激。