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

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

按真正需要的起点计算¶

当 \(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。