给定n顶点上的加权有向无圈图，这样每个顶点最多具有内5度和最多外度5。节点0, 1, ..., n - 1的方向是这样的
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
...
n-5 n-4 n-3 n-2 n-1
边缘只能从一行中的节点到下一行中的某个节点。
我们将获得q查询，询问从u到的最短路径长度v。这里n可以向上10^5和q向上10^4。权重均为正整数。
我们能做得比O(nq)动态编程更好（显然在这里行不通）吗？
这似乎好得是真实的，对不起，如果它不...你可以O(n)（编辑：O(n^(4/3))）预处理和O（1）查询。
我正在考虑您知道如何及时计算图中所有节点之间的所有最短距离O(n^2)。（这确实有可能，您似乎知道）
将图形划分为k块，每个块包含n/(5*k)行。（这些块应在完整的行上开始和结束，并且两个连续的块分别在其第一行和最后一行重叠）
计算每个块中所有节点（尤其是第一行和最后一行）之间的最短路径：O((n/k)^2)。
然后可以考虑只在两个块之间的边界上包含节点的简化图，其边值等于刚计算出的两个节点之间的最短路径O(k)。及时计算该图中的所有最短路径O(k^2)。
总预处理时间：O((n/k)^2 + k^2)。以k=sqrt(n)，您将进行O(n)预处理。
然后查询时间为O(1)：取u块末尾的5个节点，v块末尾的5个节点（如果块不同），您只需要比较u-> v的25种可能性
编辑
当然是假的。实际上，您有k个要为其计算最短路径的块，因此该步骤的总复杂度为O(k*(n/k)^2)。因此，总数为O(n^2/k + k^2)，而k的最佳选择为k=n^(2/3)，这给预处理O(n^(4/3))和总数查询带来了总的复杂性O(q)
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句