企业官网建设流程全解析

CCF-CSP第35次认证的第四题《通讯延迟》，核心考点就是Dijkstra最短路加虚拟节点思想。我第一遍做的时候，没卡在Dijkstra本身，而是卡在建模：题目一上来给了一堆信号源、一堆接收站，直接跑最短路根本不知道把谁当起点。后来把“多源多汇”压缩成“单源单汇”，代码半小时写完，样例一遍过，这种建模思路的转变比背十个Dijkstra模板都管用。

这篇文章不是为了贴一份AC代码就收工。我会把这道题从场景重述、算法选择、建图推导、完整C++实现，到常见WA/TLE的坑全部讲透。不管你是正在准备CCF-CSP，还是想补一补图论建模，都可以照着复现一遍。尤其是“虚拟节点”听起来玄乎，其实理解以后就是加一个边权为0的点的事，关键是怎么想到加、加在哪里、方向怎么定。

1. 别把题面理解成“跑很多次最短路”

1.1 题目究竟问的是什么

按标题考点反推出来的模型，题面大致是这样的：有一张由N个节点、M条边组成的通讯网络，边权代表链路延迟。网络里有K个信号源，还有L个接收节点。信号从任意一个信号源发出，走一条路径到接收节点，总延迟就是路径上所有边的延迟之和。要回答的问题是：从任意信号源到任意接收节点，最小的通讯延迟是多少。

如果熟悉图论，一眼能看出这是个最短路问题。真正的难点在于，起点不是一个点，终点也不是一个点。起点是K个点的集合，终点是L个点的集合。你当然可以把K个源点挨个当作起点跑K次Dijkstra，但如果K也接近数据规模上限，这个方案在题目数据量面前是必死的。

这里先提个变体，免得后面有人对不上号。有些版本的题面问的是“所有接收节点全部收到信号的最短时间”，这种时候要的是从任意源点出发，到每个接收节点的最早到达时间，最后取最大值。那个模型只需要加一个超级源点，不需要超级汇点。下面主要讲更常见的“任意源到任意终点的最小延迟”模型，Dijkstra部分两种完全通用。

1.2 枚举源点为什么必死

假设N、M、K、L都达到2e5量级，直接对K个源点分别跑堆优化Dijkstra，复杂度是：

• 单次堆优化Dijkstra：O((N+M)logN)，约莫是7e5×18，1.3e7次操作。
• K次就是再乘2e5，大约2.5e12次操作，几小时都跑不完。
• Floyed更不用提，O(N^3)，N到2e5时物理上不可能。

所以这道题必须想办法把“多源多汇”变成只跑一次Dijkstra，这个办法就是虚拟节点。这也是为什么标题把Dijkstra和虚拟节点思想放在一起，它们是一套组合拳：Dijkstra负责算最短路，虚拟节点负责把起点和终点的数量砍到1。

2. 为什么这题非Dijkstra不可

2.1 正权图才是Dijkstra的舒适区

通讯延迟不可能是个负数，所有边权都大于等于0，这是Dijkstra能用的前提。Dijkstra的核心是贪心：每次从优先队列里弹出当前“已知距离最小”的节点u，因为所有出边权非负，后面不可能绕一条路再以更小代价回到u，所以u的dist一旦确定就不用再改。

这有点像生活中排队结账：你先处理当前队伍里看起来耗时最短的那个人，因为新增的等待时间不会为负，先处理他永远不会让后面的人更吃亏。0权边会破坏这个性质吗？不会，0也是非负的。只要图里没有负权边，Dijkstra就能跑。

如果题目里出现负权边，Dijkstra的贪心假设就崩了，必须用SPFA或者Bellman-Ford。但“通讯延迟”这种场景天然非负，所以出题人给你留的门就是Dijkstra。

2.2 和SPFA、Floyed放到一起比一比

备考的时候很容易被三个最短路算法搞得选择困难。把三个都摊开看：

SPFA为什么在这题不是好选择？它本质是Bellman-Ford的队列优化，在正权图上虽然很多时候跑得快，但构造性数据能把它卡到O(NM)。CCF-CSP这种级别的数据量，用SPFA就是赌数据不卡你，没必要。堆优化Dijkstra的复杂度是确切的、稳定的，这也是竞赛里遇到非负权最短路时的默认选项。

3. 虚拟节点思想：把“多源多汇”压成“单源单汇”

3.1 超级源点：给所有起点一个共同的零号站

虚拟节点思想的第一步，是处理“K个信号源”。办法是新增一个编号为0的超级源点，从0向每一个真实信号源连一条有向边，边权为0。

这个0号点就像一个快递集散中心：不管你的货物在哪个仓库，都先运到这个中心，再从中心出发统一规划路线。因为从0到每个真实源点的边权都是0，所以从0号点出发，到任意一个信号源再到网络里的其他节点，总代价和直接从那个信号源出发一模一样。

推理也很严谨：

• 原图里任意一条从某个信号源Si到节点x的路径P，对应到新图就是0号点先走0权边到Si，再走P，总权值不变。
• 反过来，新图里任意一条从0号点出发到x的路径，第一步必然是走某一条0权边到某个真实信号源Si，剩下部分还是原图里从Si到x的一条路径。
• 所以从0号点到x的最短距离，恰好等于从K个信号源分别出发到达x的最近距离。

这就是“多源变单源”。代码层面甚至可以不建0号点，直接在优先队列里把所有源点初始距离0丢进去，效果完全一样。但虚拟源点的价值在于，把这种初始化“物化”到了图结构里，后面可以继续叠加状态、叠加入边出边，这是纯代码特判做不到的。

3.2 超级汇点：终点出口也要统一收拢

处理完源点，再处理L个接收节点。做法是对称的：新增一个编号为n+1的超级汇点，从每一个真实接收节点向n+1连一条有向边，边权为0。

注意方向：一定是真实节点指向虚拟汇点，不是虚拟汇点指向真实节点。这相当于给每个接收节点开一个直达出口，信号到了任意一个接收节点，都算“成功到达”，然后汇总到n+1。

结合超级源点和超级汇点，整个问题就变成了：

• 从0号点出发。
• 经过0权边到某个信号源。
• 在原图里跑一段路径。
• 到某个接收节点后，走0权边到n+1号点。

这样0号点到n+1号点的最短路，就是题目要求的“从任意信号源到任意接收节点的最小通讯延迟”。跑一次Dijkstra，全题结束。

3.3 复杂度收益真的来自“少跑了K次”

改造之后，图的规模变化是：节点数从N变成N+2，边数从M（无向图存2M条有向边）变成2M+K+L。K和L和M同数量级时，图整体规模几乎没膨胀，复杂度还是O((N+M+K+L)log(N+2))。

和之前的O(K×(N+M)logN)相比，相当于把K这个乘数直接消灭了。这就是少跑K次Dijkstra的收益。CCF-CSP第4题这种数据规模，只有这种量级的复杂度才可能过。

4. 一份思路清晰的C++实现

4.1 链式前向星版本的完整代码

用C++贴一份我调通的核心代码。为了不受数组上限限制，我用vector实现链式前向星；如果你习惯静态数组，改成固定大小head和edge也一样。

#include <bits/stdc++.h> using namespace std; using LL = long long; const LL INF = (LL)4e18; struct Edge { int to, nxt; LL w; }; vector<Edge> ed; vector<int> head; void addEdge(int u, int v, LL w) { ed.push_back(Edge{v, head[u], w}); head[u] = (int)ed.size() - 1; } vector<LL> dist; void dijkstra(int S, int N) { dist.assign(N, INF); priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> pq; dist[S] = 0; pq.push(make_pair(0, S)); while (!pq.empty()) { LL d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) continue; for (int e = head[u]; e != -1; e = ed[e].nxt) { int v = ed[e].to; LL nd = d + ed[e].w; if (nd < dist[v]) { dist[v] = nd; pq.push(make_pair(nd, v)); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; while (cin >> n >> m) { // 节点编号：1..n 为原图节点，0 为超级源点，n+1 为超级汇点 head.assign(n + 2, -1); ed.clear(); for (int i = 0; i < m; ++i) { int u, v; LL w; cin >> u >> v >> w; addEdge(u, v, w); addEdge(v, u, w); // 无向图 } int k; cin >> k; while (k--) { int s; cin >> s; addEdge(0, s, 0); // 超级源点 -> 每个信号源 } int l; cin >> l; while (l--) { int t; cin >> t; addEdge(t, n + 1, 0); // 每个接收节点 -> 超级汇点 } dijkstra(0, n + 2); if (dist[n + 1] >= INF / 2) cout << -1 << '\n'; else cout << dist[n + 1] << '\n'; } return 0; }

如果你确认题目只有一组输入，把外层while去掉，换成单组读入也是一样的。多组输入的清理方式我放在第5章细讲。

4.2 关键代码段逐段拆解

第一个重点：为什么用链式前向星而不是vector邻接表。链式前向星本质上就是把邻接表数组化，边存在一个大的vector里，每个节点用head记录第一条边的下标，nxt串起这个节点的所有边。优点是内存连续、遍历时缓存友好，在M到50万级别时比vector<vector >省不少分配开销。不想手写也可以，vector邻接表直接能过，但这道题如果出现在CCF-CSP第4题，链式前向星这种更稳定的写法能帮你省下被卡常数的风险。

第二个重点：dist和w都必须是long long。单条边权给到1e9很常见，路径上叠几万条边，总和很容易突破int范围。用int存w加上int存dist，WA是迟早的事。这里INF设成4e18，一是路径总长不可能到这个量级，二是做d+w时不会溢出long long。

第三个重点：优先队列。priority_queue默认是大顶堆，必须传greater<pair<LL,int>>才是小顶堆，每次弹出的才是当前距离最小的节点。忘写greater等于白写Dijkstra，直接变贪心错误算法。弹出后用if (d > dist[u]) continue跳过旧节点，等于是用距离判断替代了visited标记，不额外开数组，也避免了重复扩展。

第四个重点：C++版本兼容。CCF-CSP评测环境如果只开C++14，结构化绑定auto [d, u] = pq.top()可能编译不过，稳妥写法就是用.first和.second。代码里我已经全部避开了。

4.3 手算样例验证一遍

给一组我自己调试时的样例：

4 4 1 2 5 2 3 1 1 3 10 2 4 3 2 1 2 2 3 4

意思是4个节点、4条无向边，信号源是1和2，接收节点是3和4。手算一下：从源2到接收3延迟是1，从源2到接收4延迟是3，所以答案应该是1。

改造后的图上，0号点连向1和2，权0；节点3和4连向5号点，权0。Dijkstra过程如下：

最终dist[5]=1，和手算一致。代码跑出来的输出就是1。

5. 四个WA/TLE高发点，我几乎全踩过

5.1 虚拟边的方向写反，样例却照样过

最容易翻车的地方就是虚拟汇点的方向。接收节点到超级汇点，必须是addEdge(t, n+1, 0)，而不是addEdge(n+1, t, 0)。

我第一次写反了方向，小样例竟然AC，因为当时目标节点集合里有一个节点同时也被别的路径经过，歪打正着。换一组数据直接WA。想清楚逻辑就知道：如果从n+1指向真实接收节点，那么Dijkstra从0号点出发根本走不到n+1，除非原图有一条边能绕回，那就变成了一条完全不该存在的路径。

检查方法很土但有效：跑完样例后，把dist数组打出来，看看源点集合和目标节点集合的dist是否分别等于预期的最短路，而不是只盯着dist[n+1]看。多花三十秒，能省一次提交。

5.2 距离类型没用long long，累加直接溢出

我有一版代码用int存了dist，样例和数据规模小的测试全过，数据一大就开始出现“某些距离变成负数”的诡异结果。原因就是路径总和超过了int上限。

算法竞赛里只要边权超过1e9，或者路径可能经过超过3万条边，就要果断long long。这道题通讯网络规模大，单条延迟给到1e9完全可能，路径上一串加起来就是5e13这种量级。int只有2.1e9，指数级不够。看到“权值、距离、方案数”这几个词，第一反应先上long long，不会错。

5.3 多组输入时数组残留，WA到怀疑人生

如果你是像我一样用while(cin>>n>>m)处理多组数据，必须记得每组数据前重新初始化head和ed。链式前向星的head数组如果不复原成-1，旧边会被当成新边的一部分遍历到，结果就是整张图多出一堆幽灵边，dist全乱。

我踩过的具体操作是：写了ed.clear()但忘了head.assign(n+2, -1)，导致旧head残留。后来在init里统一写上这两行，问题消失。如果用的是vector<vector<pair<int,LL>>> g，那就要g.assign(n+3, vector<pair<int,LL>>())或者每组分批clear。

5.4 优先队列、读入优化、堆里旧节点处理

优先队列的坑不止大顶堆一个。每次松弛成功都会push一个新的pair进堆，同一个节点可能因为被不同路径反复更新而出现在堆里好几份。如果不加if (d > dist[u]) continue，弹出一份旧数据后还会继续扩展它，虽然算法结果往往还对，但运行时间会被没必要的重复扩展拉长，数据一大就变成TLE。

读入优化也不要省。ios::sync_with_stdio(false); cin.tie(0);两行写上去。M到50万时，cin默认和stdio同步会慢到怀疑人生。如果你连这两行都不想写，那就自己写快读。实测同一份Dijkstra，加不加这两行，在50万条边的数据上时间能差两倍以上。

6. 把“虚拟节点”提炼成可迁移的解题模板

6.1 触发条件：看见这些词就警觉

刷题多了会发现，虚拟节点不是某一道题的奇技淫巧，而是一类建模套路。当题面出现下面这些信号时，就可以条件反射地画一个超级源点或者超级汇点：

• 题目里明确说“有多个起点”或者“任意一个起点都可以”。
• 题目里有多个终点/出口，求的是“到达任意一个即可”的最值。
• 多个起点之间存在相同的初始状态，比如初始时间都是0、初始代价都相同。
• 网络流里出现多源多汇，需要合并成超级源点和超级汇点。
• 分层图最短路里，不同状态之间需要通过虚拟的状态点来转移。

看到这些信号，先别急着写枚举，停下来问一句：能不能在图上多放一个0权点，让所有起点从这个点出发，或者所有终点都汇聚到这个点？

6.2 一个通用模板代码

把建图这一步抽象出来，模板大概是这样的：

// 节点编号约定：1..n 原图；0 超级源点；n+1 超级汇点 vector<vector<pair<int, LL>>> g(n + 3); // 读入原图边 for (int i = 0; i < m; i++) { int u, v; LL w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向图 } // 超级源点连接所有源点 for (auto s : sources) { g[0].push_back({s, 0}); } // 所有终点连接超级汇点 for (auto t : targets) { g[t].push_back({n + 1, 0}); } // 然后跑一次 dijkstra(0, n + 2)，答案在 dist[n+1]

如果你不想加虚拟源点，等价写法是：在dijkstra最开始，把所有源点的dist初始化为0并全部push进优先队列。效果一样，但真正遇到多源最短路+其它状态转移时，虚拟源点更统一、更好推理。我建议两个都理解，考场上哪个顺手用哪个。

6.3 同款思想在另外三类题里的用法

第一类是网络流。最大流模板里常常有多个供应点和多个需求点，标准做法就是加一个超级源点S连所有供应点，容量INF；所有需求点连超级汇点T，容量INF。这和通讯延迟这道题的思路一模一样，只是把边权换成了容量。

第二类是多源BFS/0-1 BFS。比如网格题让你求“每个格子到最近的地铁站的距离”，如果每个地铁站都做一次BFS就太慢了。正确做法是所有地铁站初始距离0一起入队，一次BFS搞定。这其实就是多源最短路的雏形，边权为1或者0时，BFS的队列天然就是那个“虚拟源点”。

第三类是分层图最短路。有些题需要区分状态，比如“没使用优惠券”和“已经使用了优惠券”。把这两种状态建成两层图，两层之间加一条特殊权值的边，求最短路时其实也是在借助虚拟节点做状态转移。题目包装再花哨，本质还是图上的一个点代表“某个阶段的某个位置”，虚拟节点代表“状态之间的跳转”。

最后说点考场体会。图论题最怕的不是不会Dijkstra，而是不会把题目语言翻译成图。你一旦习惯了“多个起点=超级源+0权边”“多个终点=超级汇+0权边”这套动作，看到这类题很快就能判断能不能套。这个思维不止对CCF-CSP有效，很多带一点网络流、带一点分层图影子的问题也共用同一套逻辑。把这道题的代码彻底跑熟，再多找两道多源BFS练手，虚拟节点的感觉会非常快到位。