Ant*_*ith 6 algorithm graph-theory shortest-path graph-algorithm
我正在尝试解决这个问题：https : //cses.fi/problemset/task/1160/
基本上，这个问题要求编码器Q在后继N节点图中处理最短路径查询，其中Q和N的数字高达 100000。我已经被这个问题困住了好几天，我的想法都不够快，可以通过所有测试用例。
我的第一个想法是使用某种全对最短路径算法，例如 Floyd-Warshall 算法。然而，这种算法将在运行O(N^3 + Q)时间，这是方法太慢了这个问题。
我的第二个想法是使用广度优先搜索单独处理每个查询。这个算法会O(Q*N)及时运行，这比我的第一个想法快，但对于问题来说仍然太慢。
我尝试在网上搜索解决方案，但没有找到任何解释。有人可以指出我正确的方向吗？