# 终点和起点: 题解

出题人解法：添加虚拟起点与终点，运行 Dijkstra。Codex（GPT-6）整理 C++17 实现、空集合与距离范围说明，补充直接多源初始化方案。

## 把任意选择端点变成一次最短路

添加虚拟起点 $s_0$ 和虚拟终点 $t_0$ .从 $s_0$ 向每个 $S$ 中的点添加零权有向边；从每个 $T$ 中的点向 $t_0$ 添加零权有向边。原无向边在邻接表中存成两个方向。

每条原题路径可以在两端添加这两条零权边，得到同权的 $s_0$ 到 $t_0$ 路径。反过来，虚拟起点只有出边，虚拟终点只有入边，所以任何这样的路径中间部分都连接一个合法起点和一个合法终点。两者最小值相同；某个集合为空时，虚拟两点无法连通。

## 非负权最短路

令起点距离为零，其余为无穷大。用最小堆选择当前最小候选距离，沿出边松弛邻居；每次严格变短才入堆。堆中可能保留过时记录，弹出距离与数组不符时直接跳过。

Dijkstra 的正确性来自非负边权。尚未确定的点中距离最小者不可能再通过另一个尚未确定的点得到更短路径：路径第一次跨出已确定集合的边已被松弛，而后续边不降低长度。归纳可知每次首次弹出的有效最小距离都是真实最短距离。最终读取虚拟终点距离，无穷大则输出负一。零权边、平行边与自环不影响证明。

## 复杂度、范围和补充方案

扩展图有 $n+2$ 个点、$O(n+m)$ 条有向边。使用允许过时项的二叉堆，总时间 $O((n+m)\log(n+m+1))$ ，空间 $O(n+m)$ .这里允许重边，因此直接用边数界定堆规模，而不无条件把对数写成只依赖顶点数。

非负权图的最短路可以取简单路径，原图有限答案至多 $(n-1)\cdot10^9<5\times10^{14}$ .用 64 位有符号距离，选择足够大且相加安全的哨兵。程序只从有限距离进行松弛。

[std.cpp](std.cpp) 保留虚拟点建模；[直接多源 Dijkstra](solution-alternative.zh.md)同时把所有合法起点设为零，省去虚拟边，表达更直接。两者同阶并支持全部数据，不把这种建模简化描述成渐进优化。逐个起点重复求最短路会引入 $\lvert S\rvert$ 倍工作，没有相应优势。