一种图算法

Question

有一个算法问题我真的搞不懂。这个问题可以使用Dijkstra算法。

有一个由n台计算机组成的网络，你可以黑它来控制。最初，您已经黑进了计算机c0。计算机之间有许多连接，你可以通过它从被黑的计算机中取出一台失控的计算机。每个连接都被描述为一个三重(ca；cb；t)，这意味着如果ca被黑客攻击，那么您可以以t分钟的代价成功地攻击cb。

一大群你的黑客朋友加入你的黑客活动(他们和你一样优秀，和网络中的电脑一样多)。它们都由您命令，这意味着您可以同时在多台计算机上分配黑客任务。描述一个特定的算法，以确定成功攻击网络中的所有计算机所需的时间。用n，m表示运行时间。

Answer 1

让您的计算机被标记为c_0, c_1, ..., c_{n - 1}。运行Dijkstra之后，您要寻找的答案是max { d[i] | 0 <= i <= n - 1}，其中d[i]表示c_0和c_i之间的最小距离。这是正确的，因为: 1)您至少需要时间等于所有这些距离的最大值，才能破解最遥远的计算机；2)看看我们在应用Dijkstra算法后得到的树(c_0将是该树的根)。我们可以采用以下策略:首先，我们开始对c_0的所有邻居进行黑客攻击，然后继续攻击所有已经被黑客攻击的计算机。我们这样做直到所有的电脑都被黑了。我们可以看到，这种情况发生所需的时间将等于树的最大深度(请注意，这棵树的边缘的权重等于原始图的权重)。我们可以很容易看到，这个数字与我们刚才所说的完全相同。所以总运行时间等于Dijkstra的O(m + nlogn)