# 两类最短路查询: 补充解法

贡献：Codex（GPT-6）补充按询问起点分组的稠密 Dijkstra。大图单询问沿用出题人的堆优化 Dijkstra；与 Floyd 的比较见[首选题解](solution.zh.md)。

## 按真正需要的起点计算

当 $n\le500$ 时，用邻接矩阵保存任意两点间最小的直接边权，对角线为零，不相邻为无穷大。读入全部询问，按起点存储终点与原询问编号。仅对非空分组运行一次 Dijkstra。

小图的 Dijkstra 不需要堆：每轮扫描所有未确定点，选择距离最小者，再扫描其一整行矩阵进行松弛。没有有限的未确定点时结束。随后把该组各终点的距离填入其原编号位置，全部组完成后按输入顺序输出。

## 正确性与复杂度

同一起点的所有询问只取决于同一份单源距离。矩阵对重边取最小值不改变任何最短路；更重的直接边总能由端点相同的最轻边代替。稠密扫描与最小堆只是选取当前最小候选的不同方式，仍满足非负权 Dijkstra 的确定顺序与证明。因此每组获得正确距离，原编号恢复顺序后每个答案正确。

令 $r$ 为不同询问起点数。读边、分组、计算和输出共 $O(m+rn^2+q)$ 时间，空间 $O(n^2+q)$ .当 $r$ 很小时，避免了为无用起点计算距离；最坏 $r=n$ 时仍为三次时间，并多用了存储询问与答案的空间。大图时仍有 $q=1$ ，沿用堆 Dijkstra 的 $O((n+m)\log(n+m+1))$ 时间和 $O(n+m)$ 空间。

该方案支持完整数据范围，作为按实际查询分布选择的并列方法。它保留 64 位距离与安全哨兵，支持同点查询、零权边、重边和不连通图。程序：[alternative.cpp](alternative.cpp)。