两类最短路查询: 题解¶

出题人解法：小图使用 Floyd，全范围单询问使用堆优化 Dijkstra。Codex（GPT-6）整理 64 位距离、重边与对角线初始化，并补充按询问起点分组的稠密 Dijkstra 方案。

范围决定两条计算路径¶

当 \(n\le500\) 时，可以先计算所有点对距离，再逐次查表。否则，全局保证迫使 \(q=1\) ，只需求这一个起点到各点的最短距离。两种情况合起来覆盖全部正式输入。

用矩阵 \(D\) 存储距离：对角线为零，其余为无穷大；每条无向边更新两个方向，遇到重边保留最小值。按 \(k=1,\ldots,n\) 依次允许一个新的中间点，执行

\[ D_{i,j}\leftarrow\min(D_{i,j},D_{i,k}+D_{k,j}) \]

第 \(k\) 轮后，矩阵表示中间点只允许来自 \(1,\ldots,k\) 的最短路。证明：最优简单路径或不经过 \(k\) ，或经过它并分成两段，后者的中间点都在更小集合中；分别由旧值与两段距离之和表示。非负权保证可取简单路径。初始矩阵是无中间点的情形，归纳后所有路径都被涵盖。

时间 \(O(n^3+m+q)\) ，空间 \(O(n^2)\) .输出可直接逐条查询，无需保存所有询问。

用邻接表存边，将询问起点距离设为零，其他设为无穷大。每次弹出最小堆中的有效最小距离，松弛邻居，丢弃过时堆项。非负权保证未确定的点不能通过更晚确定的点得到更小距离：任何这样的路径第一次跨出已确定集合时，已经给出不大于其完整长度的候选。由此归纳，弹出有效最小项时距离正确。

堆中条目数受边数控制，时间 \(O((n+m)\log(n+m+1))\) ，空间 \(O(n+m)\) .只回答唯一的询问；不可达输出负一。

有限最短路不超过 \((n-1)\cdot10^9<5\times10^{14}\) ，必须使用 64 位距离。无穷大取有符号 64 位最大值的四分之一，两个哨兵相加仍安全。矩阵对角线始终从零开始，自环不会使它变大。判断不可达使用哨兵，不以某个较小阈值代替。

std.cpp 采用以上两种出题人算法。按起点分组在小图上只为实际询问到的起点计算距离，使用稠密 Dijkstra，时间为 \(O(m+rn^2+q)\) ，其中 \(r\) 是不同询问起点数。起点少时工作更少，但需要保存询问，并且最坏时间仍为三次；它作为并列方案支持全部范围。