我将尝试做出清晰的类比：
[有一个城市有N个目的地。它由加权有向图表示，其中权重是距离（以分钟为单位）。
[有两个人不想同时在同一目的地。他们位于不同的目的地。他们将使用最短路径前往另一个目的地，而根本不在同一目的地。他们将在每个访问的目的地停留M分钟。
如何在保持最远距离的同时找到最短路径？
注意：我已经看过最短路径算法，旅行商算法和其他变体。但是我不知道如何有效地解决它。查找所有路径并比较交叉点看起来并不划算。
[用C1！= C2构造城市对（C1，C2）的图，C1，C2和C1'，C2'之间的边的权重为dist（C1，C1'）+ dist（C2，C2'）+ M.请注意，如果C1 = C1'或C2 = C2'中的一个表示没问题，则代表一个旅行者不动的情况（例如，如果他们已经到达目标城市）。
现在，从起点城市（S1，S2）到终点城市（E1，E2）的最短组合路径是两个乘积者从未同时位于同一地点的最短路径。
因此，您必须构造一个新图，但是您可以使用dijkstra的算法或任何其他最短路径算法来找到解决方案。