在动态图中找到最短路径
Find shortest path in dynamic graph
让我们看看我们的示例输入：
10.01.2013 CREATE road between 1 and 2 with maximum speed 90 and distance 120
25.03.2013 CREATE road between 1 and 4 with maximum speed 110 and distance 25
13.07.2013 CREATE road between 2 and 3 with maximum speed 160 and distance 320
19.07.2013 MODIFY road between 1 and 4 with maximum speed 120
01.11.2013 CREATE road between 1 and 3 with maximum speed 30 and distance 34
21.11.2013 MODIFY road between 2 and 3 with maximum speed 130
30.12.2013 CREATE road between 2 and 4 with maximum speed 80 and distance 120
当我们修改图表时，速度只能提高。
好的，我需要回答问题。例如：
When time travel between 1 and 4 will be shorter than 20 minutes
When time travel between 2 and 4 will be shorter than 70 minutes
最大查询数为 10。
这是示例，随机数据仅用于解释我的问题。
我使用 dijkstra 算法回答这个问题，但我 运行ning Dijkstra 用于图形的每个修改中的每个查询。因此，如果我有 10 000 个修改和 10 个查询，我的解决方案将 运行 100 000 次 Dijkstra 算法。我知道这很糟糕，但这次我找不到更好的解决方案，所以我在这里写信寻求帮助。我可以补充一点，最大顶点数为 10 000，最大边数为 100 000。
由于图形修改只能缩短从 A 点到 B 点的行进时间，因此以下观察结果为真：
For modifications m1 and m2 such that m1 is earlier than m2 and travel times between the same points A and B, T1 and T2, it is true that T1 >= T2
这一观察让我们可以使用 divide and conquer strategy（本质上是二分搜索）来回答查询：选择一个中点，使用 Dijkstra 算法找到旅行时间，然后根据结果向中点的右侧或左侧移动.
现在你需要解决一个问题，即在构建到某个修改点的图中找到一条路径。您可以通过使用 {time, speed} 对的列表来增加每条边，并通过在附加到该边的排序地图中查找来获得速度。
Dijkstra 算法运行 O(q * log2m) 次，其中 m 是修改次数，q 是查询次数。
您快完成了，您只需要进行一些优化。
我认为这里的要点是路径只能变得更短。所以对于查询，答案是第一次满足。
所以这是我建议的修改。
- 你 运行 Dijkstra 在初始图上像以前一样。
- 按时间顺序对更新进行排序。
- 检查是否满足条件，满足则停止
- 选择下一个更新，看看您是否可以使用它来改进到使用新路径的任一节点的最小距离。
- 如果没有改善转4
- 如果有改进，将更新的节点推入 Dijkstra 优先级队列并继续 运行ning dijkstra 直到您再次清空队列。
- 转到 3 并继续。
想象一下，图表的节点不仅是数字，而且带有日期的数字和链接也有日期。然后搜索这个修改后的图表。
让我们看看我们的示例输入：
10.01.2013 CREATE road between 1 and 2 with maximum speed 90 and distance 120
25.03.2013 CREATE road between 1 and 4 with maximum speed 110 and distance 25
13.07.2013 CREATE road between 2 and 3 with maximum speed 160 and distance 320
19.07.2013 MODIFY road between 1 and 4 with maximum speed 120
01.11.2013 CREATE road between 1 and 3 with maximum speed 30 and distance 34
21.11.2013 MODIFY road between 2 and 3 with maximum speed 130
30.12.2013 CREATE road between 2 and 4 with maximum speed 80 and distance 120
当我们修改图表时，速度只能提高。
好的，我需要回答问题。例如：
When time travel between 1 and 4 will be shorter than 20 minutes
When time travel between 2 and 4 will be shorter than 70 minutes
最大查询数为 10。
这是示例，随机数据仅用于解释我的问题。
我使用 dijkstra 算法回答这个问题，但我 运行ning Dijkstra 用于图形的每个修改中的每个查询。因此，如果我有 10 000 个修改和 10 个查询，我的解决方案将 运行 100 000 次 Dijkstra 算法。我知道这很糟糕，但这次我找不到更好的解决方案，所以我在这里写信寻求帮助。我可以补充一点，最大顶点数为 10 000，最大边数为 100 000。
由于图形修改只能缩短从 A 点到 B 点的行进时间，因此以下观察结果为真：
For modifications m1 and m2 such that m1 is earlier than m2 and travel times between the same points A and B, T1 and T2, it is true that T1 >= T2
这一观察让我们可以使用 divide and conquer strategy（本质上是二分搜索）来回答查询：选择一个中点，使用 Dijkstra 算法找到旅行时间，然后根据结果向中点的右侧或左侧移动.
现在你需要解决一个问题，即在构建到某个修改点的图中找到一条路径。您可以通过使用 {time, speed} 对的列表来增加每条边，并通过在附加到该边的排序地图中查找来获得速度。
Dijkstra 算法运行 O(q * log2m) 次，其中 m 是修改次数，q 是查询次数。
您快完成了，您只需要进行一些优化。 我认为这里的要点是路径只能变得更短。所以对于查询，答案是第一次满足。 所以这是我建议的修改。
- 你 运行 Dijkstra 在初始图上像以前一样。
- 按时间顺序对更新进行排序。
- 检查是否满足条件，满足则停止
- 选择下一个更新，看看您是否可以使用它来改进到使用新路径的任一节点的最小距离。
- 如果没有改善转4
- 如果有改进，将更新的节点推入 Dijkstra 优先级队列并继续 运行ning dijkstra 直到您再次清空队列。
- 转到 3 并继续。
想象一下，图表的节点不仅是数字，而且带有日期的数字和链接也有日期。然后搜索这个修改后的图表。