1. 从一道经典题看多源最短路的破局思路
第一次碰到“多起点、单终点”的最短路问题，很多人下意识会想：把每个起点都跑一遍单源最短路，然后取最小值不就行了？这个思路没错，但复杂度直接乘以起点数量，遇到起点多、图又大的情况，时间直接爆炸。HDU 2680 这道题就是典型的“多源最短路”场景，而它给出的标准解法——虚拟源点——是我个人认为在图论入门阶段最值得反复咀嚼的一个技巧。
这道题的大意是：给定一个有向图，再给定若干个可能的起点和一个固定的终点，问从任意一个起点出发到达终点的最短距离是多少。如果无法到达，输出 -1。题目本身不复杂，但它背后引出的“虚拟源点”思想，在后续很多问题里都会反复出现，比如多源BFS、多源最短路、带超级源点的网络流建模等等。
这篇文章我会从零开始，把这道题的思路、实现、坑点、以及虚拟源点这个技巧的通用价值全部拆开讲清楚。不管你是刚学最短路的新手，还是想复习一下建模技巧的老手，应该都能从中拿到一些可以直接复用的东西。核心关键词就三个：多源最短路、虚拟源点、Dijkstra。我会用最直白的方式把它们串起来。
2. 问题本质与朴素解法的复杂度分析
2.1 题目到底在问什么
先把问题抽象一下。有一个有向图，边带非负权值。给一个终点集合里的唯一终点T，再给一个起点集合S = {s1, s2, ..., sk}。要求的是：
min{ dist(si, T) | si ∈ S }也就是所有起点到终点距离里的最小值。注意方向：是起点到终点，不是终点到起点。这个方向性很关键，后面会讲到反向建图的技巧。
如果只有一个起点，那就是标准的单源最短路，Dijkstra 或 SPFA 随便跑。但这里有 k 个起点，k 可能很大，问题就变成了多源最短路。
2.2 朴素做法：每个起点跑一次
最直接的想法就是暴力：对每个起点 si 跑一次 Dijkstra，算出 dist(si, T)，然后取最小。假设图有 n 个点、m 条边，单次 Dijkstra 用优先队列优化是 O((n+m) log n)，跑 k 次就是 O(k(n+m) log n)。
这个复杂度在 k 比较小的时候还能接受，但题目里 k 完全可以和 n 同阶。一旦 k 接近 n，复杂度就退化成 O(n(n+m) log n)，对于 n 上万、m 上十万的图来说，基本就是超时的命。我实测过，这种规模下朴素做法在主流评测环境里跑几秒都出不来结果。
所以问题的核心矛盾是：起点太多，逐个处理代价太高。我们需要一种方式，把“多源”这件事在一次最短路计算里解决掉。
2.3 另一个角度：反向建图
在讲虚拟源点之前，先提一个很多人会想到的替代方案：反向建图。因为题目问的是“起点到终点”，如果我们把所有边反向，问题就变成“从终点出发，到任意一个起点的最短距离”。这样只需要从终点跑一次单源最短路，然后检查所有起点里哪个 dist 最小即可。
这个思路是对的，而且复杂度只有一次 Dijkstra，非常优秀。但它有一个前提：图必须能反向，而且问题必须是“多起点到单终点”这种特定结构。如果题目变成“多起点到多终点”，或者起点和终点都是集合，反向建图就不够用了。而虚拟源点的适用范围更广，所以它才是更通用的解法。这也是为什么我更愿意把虚拟源点作为主推方案来讲。
3. 虚拟源点：一个点解决所有起点
3.1 核心思想拆解
虚拟源点的思路其实特别朴素：既然有 k 个起点，那我干脆造一个“超级起点”，让它到每个真实起点的距离都是 0，然后从这个超级起点跑一次单源最短路。这样算出来的 dist(T) 就是“超级起点到 T 的最短距离”，而超级起点到 T 的任意一条路径，必然是“超级起点 -> 某个真实起点 -> ... -> T”，由于超级起点到真实起点的边权是 0，所以这条路径的长度就等于那个真实起点到 T 的距离。
于是，一次 Dijkstra 就能得到所有起点到终点的最小值。复杂度从 O(k(n+m) log n) 直接降到 O((n+m) log n)，和单源最短路一模一样。
用一个生活化的类比：你要从好几个不同的家出发去同一个公司，想知道哪个家离公司最近。虚拟源点相当于在你所有家门口都修了一条“传送带”，传送带本身不花时间，你只要先站到传送带上，就等价于从任意一个家出发。这样你只需要算一次“从传送带网络到公司”的最短路。
3.2 为什么边权设为 0 而不是其他值
这里有个细节值得说清楚：虚拟源点到每个真实起点的边权必须设为 0。为什么？因为我们要保证“从虚拟源点出发到真实起点”这一段不引入额外代价。如果设成其他值，比如 1，那最终算出来的距离就会多出这个常数，结果就错了。
从数学上看，我们要求的是 min over si of dist(si, T)。构造虚拟源点 S' 后，dist(S', T) = min over si of (w(S', si) + dist(si, T))。要让这个式子等于我们想要的结果，必须 w(S', si) = 0 对所有 si 成立。这是虚拟源点能成立的关键前提，不能想当然。
3.3 虚拟源点的通用性
这个技巧不只用于最短路。多源 BFS 里，把所有源点一开始全部入队，本质上就是虚拟源点思想——队列里初始的那一批点，等价于从一个虚拟源点同时出发。网络流里加超级源点、超级汇点，也是同一个套路。甚至在一些动态规划的多起点问题里，也可以人为构造一个“起始状态”来统一处理。
所以掌握虚拟源点，不只是会做一道题，而是拿到了一把能开很多把锁的钥匙。我在后面会专门讲几个它的变体和扩展场景。
4. 完整实现：从建图到输出
4.1 图的存储方式选择
这道题我推荐用链式前向星或者邻接表 + 边结构体来存图。原因是虚拟源点会额外增加 k 条边，如果用邻接矩阵，空间是 O(n^2)，n 稍微大一点就爆内存。邻接表空间是 O(n+m)，更适合。
具体来说，我会用一个head数组记录每个点的第一条边，nxt数组记录下一条边的下标，to和w分别记录终点和权值。这是竞赛里最常用的写法，插入边是 O(1)，遍历某个点的所有出边也是 O(度数)。
如果你用 Python，可以用defaultdict(list)或者列表套列表来存邻接表，效果一样，只是常数大一些。下面我以 C++ 风格伪代码为主，因为这道题原题就是 C++ 环境，但思路对任何语言都通用。
4.2 虚拟源点的编号与建边
虚拟源点的编号通常取0，而真实点从1到n。这样不会和真实点冲突。建图时，先读入所有真实边，然后对于每个给定的起点 si，加一条从 0 到 si、权值为 0 的有向边。
这里有个容易踩的坑：虚拟源点到起点的边是有向的，方向是 0 -> si。不要加成无向边，也不要把方向搞反。因为我们要模拟的是“从虚拟源点出发，第一步走到某个真实起点”，方向反了就变成“从起点走到虚拟源点”，逻辑完全错了。
另外，如果题目给的起点有重复，加边时重复加也没关系，Dijkstra 会自动处理，只是稍微浪费一点空间。如果想优化，可以在加边前用个标记数组去重。
4.3 Dijkstra 的核心流程
Dijkstra 的流程我快速过一遍，重点讲和虚拟源点相关的部分：
- 初始化
dist数组全部为无穷大，dist[0] = 0，把 0 号点入优先队列。 - 每次从队列里取出当前距离最小的点 u，如果 u 已经被访问过就跳过。
- 遍历 u 的所有出边 (u, v, w)，如果
dist[u] + w < dist[v]，就更新dist[v]并把 v 入队。 - 重复直到队列为空。
最后检查dist[T]，如果还是无穷大就输出 -1，否则输出dist[T]。
这里的关键是：起点是虚拟源点 0，不是任何真实起点。很多人写着写着就习惯性地把某个真实起点入队，那就退化成单源了。
4.4 完整代码框架
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; const int MAXM = 20005; const int INF = 0x3f3f3f3f; struct Edge { int to, w, nxt; } edges[MAXM]; int head[MAXN], cnt; int dist[MAXN]; bool vis[MAXN]; void init() { memset(head, -1, sizeof(head)); cnt = 0; } void addEdge(int u, int v, int w) { edges[cnt].to = v; edges[cnt].w = w; edges[cnt].nxt = head[u]; head[u] = cnt++; } void dijkstra(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = head[u]; i != -1; i = edges[i].nxt) { int v = edges[i].to, w = edges[i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } } int main() { int n, m, t; while (cin >> n >> m >> t) { init(); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; addEdge(u, v, w); } int k; cin >> k; for (int i = 0; i < k; i++) { int s; cin >> s; addEdge(0, s, 0); // 虚拟源点到真实起点，权值 0 } dijkstra(0, n); if (dist[t] == INF) cout << -1 << endl; else cout << dist[t] << endl; } return 0; }这段代码里，addEdge(0, s, 0)就是虚拟源点的核心操作。注意dist数组大小要开到n+1，因为多了 0 号点。INF用0x3f3f3f3f是竞赛里的常见做法，两个 INF 相加不会溢出 int。
5. 参数细节与边界情况处理
5.1 无穷大的选取
INF的选取看起来是小事，但踩过坑的人都知道它有多重要。如果用INT_MAX，在松弛操作里dist[u] + w就可能溢出，变成负数，导致错误更新。用0x3f3f3f3f的好处是它大约是 10^9 量级，两个相加还在 int 范围内，而且memset时可以直接用0x3f填充每个字节，得到的就是这个值。
如果题目边权可能很大，比如达到 10^9，那0x3f3f3f3f可能不够用，这时候要换成long long和0x3f3f3f3f3f3f3f3f。这道题边权范围不大，用 int 就够。
5.2 重边与自环
题目可能给出重边，也就是两个点之间有多条边。邻接表存图天然支持重边，Dijkstra 会自动选择更短的那条，不需要特殊处理。自环（u 到 u 的边）也不影响，因为dist[u] + w < dist[u]在 w 非负时永远不成立，会被自动忽略。
但要注意：如果题目允许负权边，Dijkstra 就不能用了，得换 SPFA 或 Bellman-Ford。这道题边权非负，所以 Dijkstra 是安全的选择。
5.3 起点包含终点的情况
如果某个起点恰好就是终点 T，那么从虚拟源点 0 到 T 的路径就是 0 -> T，权值 0，最终答案是 0。这个情况在代码里能自然处理，不需要特判。但如果你用反向建图的思路，就要注意终点到自己的距离是 0，也要能正确输出。
5.4 无法到达的情况
如果所有起点都到不了终点，dist[T]会保持 INF，输出 -1。这里要确保 INF 的判断用的是==而不是>=，因为 dist 可能被更新成其他大值，但不会超过 INF。用dist[t] == INF是安全的。
6. 常见问题与排查技巧实录
6.1 为什么我的答案总是比正确值大
这是最常见的问题，八成是虚拟源点的边权设错了。检查一下addEdge(0, s, 0)里的第三个参数是不是 0。如果写成了 1 或者其他值，最终答案就会多出这个常数。我见过有人写成边权为 1，结果所有答案都大 1，排查半天才发现。
另一个可能原因是：虚拟源点的边加成了双向边。如果加成双向，相当于真实起点也能以 0 代价回到虚拟源点，虽然不一定影响最终结果，但逻辑上是错的，可能在某些图上引发意外。
6.2 队列里为什么有重复的点
Dijkstra 用优先队列时，同一个点可能被多次入队，因为每次松弛成功都会 push 一次。这是正常现象，用vis数组标记已处理的点即可。取出时如果vis[u]为真就跳过。不要试图在 push 前判断是否已在队列里，那样反而会增加复杂度。
6.3 多组输入没有清空数组
这道题是多组输入，每组都要重新初始化head、cnt、dist、vis。如果忘了清空，上一组的数据会污染下一组，导致莫名其妙的错误。我的习惯是把初始化写成一个init()函数，每组开头调用一次，不容易漏。
6.4 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 |
|---|---|---|
| 答案偏大固定值 | 虚拟源点边权非 0 | 检查 addEdge 第三个参数 |
| 答案偏小或为 0 | 虚拟源点边方向反了 | 确认是 0 -> s 而非 s -> 0 |
| 部分组答案错误 | 数组未清空 | 检查 init 是否每组调用 |
| 运行超时 | 用了朴素多源做法 | 确认只跑了一次 Dijkstra |
| 输出 -1 但应有解 | INF 判断或溢出 | 检查 INF 取值和松弛条件 |
6.5 一个容易被忽略的优化
如果起点数量 k 非常大，加 k 条边会让边数增加 k。虽然不影响复杂度量级，但常数会变大。可以在读入起点时用一个布尔数组去重，只对第一次出现的起点加边。这个优化在 k 接近 n 时能省下不少边，实测能快 10% 到 20%。
7. 虚拟源点的扩展与变体场景
7.1 多源多汇问题
如果题目变成“多个起点到多个终点”，虚拟源点依然能用，但需要再加一个虚拟汇点。做法是：建虚拟源点 S' 连所有起点（权值 0），建虚拟汇点 T' 连所有终点（权值 0，方向是终点 -> T'），然后求 S' 到 T' 的最短路。这样一次 Dijkstra 就能解决多源多汇。
这个建模方式在网络流里更常见，但最短路里同样适用。关键是虚拟汇点的边方向要正确：真实终点 -> 虚拟汇点，权值 0。
7.2 多源 BFS 中的虚拟源点
在无权图（或边权全为 1）的多源最短路里，用 BFS 代替 Dijkstra。此时虚拟源点的思想体现为：把所有源点一开始全部入队，dist 都设为 0。这等价于从一个虚拟源点同时向所有源点扩散。很多“腐烂的橘子”“01 矩阵”类题目都是这个套路。
7.3 带限制条件的最短路
有些题目会加限制，比如“路径上最多经过 k 条边”或者“必须经过某个点”。虚拟源点可以和这些技巧组合。比如分层图最短路里，虚拟源点连到每个起点的第 0 层，然后层间转移。这类组合题在进阶训练里很常见，核心还是把“多起点”统一成一个起点来处理。
7.4 反向建图与虚拟源点的取舍
前面提过反向建图。什么时候用哪个？我的经验是：
- 如果问题结构是“多起点到单终点”，反向建图更简洁，代码量少。
- 如果问题结构更复杂，比如多源多汇、或者起点终点会动态变化，虚拟源点更通用。
- 如果题目还要求输出具体路径，虚拟源点会多出虚拟边，还原路径时要跳过，稍微麻烦一点。
两种方法复杂度一样，选哪个看具体场景和个人习惯。我一般优先虚拟源点，因为它思维上更统一。
8. 我在这道题上踩过的坑与实操心得
第一次做这道题的时候，我用的就是朴素做法，每个起点跑一次 Dijkstra。当时觉得 k 不会太大，结果交上去直接 TLE。后来看了题解才知道虚拟源点，改完之后一次 AC。这个经历让我意识到：看到“多起点”三个字，第一反应就应该是虚拟源点，而不是暴力。
第二个坑是 INF 的选取。我早期习惯用1e9作为 INF，结果在松弛时dist[u] + w偶尔会超过 int 范围，虽然这道题没触发，但在其他题上翻过车。后来统一改成0x3f3f3f3f，省心很多。
第三个心得是关于多组输入的。这道题是多组，我一开始只在第一组前初始化，后面几组就错了。后来养成习惯：把初始化封装成函数，每组开头必调。这个习惯在几乎所有多组输入的题目里都适用，强烈建议养成。
最后一个技巧：如果你不确定虚拟源点建得对不对，可以先用小数据手算一遍。比如 3 个点、2 条边、2 个起点，手动模拟 Dijkstra 的过程，看看 dist 数组的变化是否符合预期。手算一遍比盯着代码看十分钟都管用。
这道题虽然简单，但它是理解“建模”这件事的绝佳入口。虚拟源点不是什么高深算法，就是一种把问题转化得更简单的思维方式。把这种思维练熟了，后面遇到多源 BFS、超级源点网络流、甚至一些 DP 的状态设计，都会觉得顺理成章。
