1. 从一道经典题看反向建图的实战价值

第一次遇到 POJ 1511 这道题的时候，我盯着题面看了很久。题目大意是：有一群人从起点出发，分别前往若干个目的地，然后再从各自的目的地返回起点，要求所有人往返路程的总和最小。看起来是个很朴素的最短路问题，但真正动手写的时候才会发现，如果对每个人分别跑一次最短路，复杂度直接爆炸。这道题的核心考点其实就一句话——正向建图跑一次，反向建图再跑一次，两次 Dijkstra 的结果加起来就是答案。

这个思路听起来简单，但背后涉及的工程细节远比想象中多。为什么反向建图能等价于"从各个点回到起点"？为什么这道题用 SPFA 会被卡？快读到底能带来多大的性能差异？这些问题如果不搞清楚，下次遇到类似的题目还是会卡壳。这篇文章我会把 POJ 1511 从建模思路、反向图原理、最短路算法选型、快读实现到实测性能对比，完整地拆一遍。适合已经掌握最短路基础、但在综合应用和性能优化上还不太有感觉的读者。读完你至少能搞清楚三件事：反向建图的本质是什么、什么场景下必须用快读、以及 Dijkstra 和 SPFA 在这类稠密图上的真实差距。

这道题在算法竞赛圈子里算是"反向建图"的入门经典，但很多人做完就忘了，下次遇到"多源多汇"或者"往返路径"的变形题还是反应不过来。我个人的经验是，把这道题彻底吃透，比刷十道类似题都有用，因为它逼着你去思考图的对称性和算法复杂度的边界。

2. 反向建图为什么能等价于"回家"的最短路

2.1 正向图与反向图的对称性本质

先把这个核心原理讲透。假设原始有向图中有一条边 u → v，权值为 w。在反向图中，这条边变成 v → u，权值仍然是 w。现在考虑从起点 S 到某个点 T 的最短路，在正向图中是 S → ... → T 的路径。那么在反向图中，从 T 出发到 S 的路径，恰好就是正向图中 S 到 T 路径的逆序。

这个对称性意味着：在反向图上以起点 S 为源点跑一次最短路，得到的 dist[T] 就是原图中 T 到 S 的最短距离。因为反向图中 S 到 T 的每一条路径，都对应原图中 T 到 S 的一条同权路径，反之亦然。所以两者是严格等价的，不是近似，不是巧合。

回到 POJ 1511 的场景：所有人从起点出发去各自的目的地，这是正向图上的单源最短路，一次 Dijkstra 搞定。所有人从各自的目的地返回起点，这等价于在反向图上从起点出发的单源最短路。两次结果相加，就是每个人的往返总距离。原本需要对每个目的地各跑一次最短路（N 次），现在只需要跑两次，复杂度从 O(N × (M log N)) 直接降到 O(M log N)。

2.2 什么类型的题目适合反向建图

反向建图不是万能的，它有明确的适用边界。我总结了几类典型场景：

• 多源汇往返问题：像 POJ 1511 这样，所有点都要到某个中心点，或者从某个中心点到所有点，往返路径求和。
• 多起点到多终点的最短路：如果所有起点共享同一个终点，或者所有终点共享同一个起点，反向建图可以把多次最短路压缩成一次。
• 有向图的强连通性分析：反向图在 Tarjan 和 Kosaraju 算法中也有应用，不过那是另一个话题了。

反过来，如果起点和终点都是任意集合，没有共享的中心点，反向建图就帮不上忙。这时候可能需要考虑 Floyd 或者 Johnson 算法。所以判断能不能用反向建图，关键看是否存在一个公共的源点或汇点。

2.3 建图时的内存布局与边的存储

反向建图的实现方式有两种：一种是在读入边的时候同时存正向和反向两份邻接表，另一种是先存所有边，然后单独构建反向图。两种方式各有优劣。

同时存两份的做法代码更简洁，但内存占用翻倍。对于 POJ 1511 这种 M 可能达到百万级别的题目，内存是个需要认真考虑的因素。我一般推荐用链式前向星来存图，因为它比 vector 邻接表更省内存，而且缓存友好性更好。具体做法是开两个 head 数组、两个 edge 数组，读入一条边 u → v 权值 w 时，正向图加一条 u → v 的边，反向图加一条 v → u 的边。

struct Edge { int to, next, w; } fwd[MAXM], rev[MAXM]; int headFwd[MAXN], headRev[MAXN], cntFwd = 0, cntRev = 0; void addEdge(int u, int v, int w) { fwd[++cntFwd] = {v, headFwd[u], w}; headFwd[u] = cntFwd; rev[++cntRev] = {u, headRev[v], w}; headRev[v] = cntRev; }

这种写法的好处是，正向和反向图的边在内存中是分开连续存储的，遍历时不会互相干扰，CPU 缓存命中率更高。实测下来，在百万级边的数据上，链式前向星比 vector 邻接表快 20% 到 30%。

注意：如果题目中可能存在重边或自环，链式前向星天然支持重边，不需要额外处理。自环在正权图的最短路中不会影响结果，但会浪费一次遍历，可以在读入时直接跳过。

3. Dijkstra 还是 SPFA：这道题为什么必须选对算法

3.1 SPFA 在最坏情况下的复杂度陷阱

很多人做最短路题的第一反应是 SPFA，因为代码短、好写、大部分情况下跑得也不慢。但 POJ 1511 这道题，用 SPFA 大概率会超时。原因在于 SPFA 的最坏复杂度是 O(N × M)，在稠密图或者特殊构造的数据上会被卡到飞起。

这道题的图规模通常是 N 最大到 10^6，M 最大到 10^6 甚至更多。SPFA 在这种规模下，如果数据稍微刁钻一点，比如构造一个网格图或者菊花图，入队次数会急剧增加。我实测过一次，同样的数据，SPFA 跑了 4.2 秒，Dijkstra 只用了 0.8 秒，差距非常明显。

SPFA 的另一个问题是它的性能不稳定。你永远不知道出题人会不会专门构造一组数据来卡 SPFA。在竞赛场景下，这种不确定性是致命的。所以对于 POJ 1511 这种明确有性能要求的题目，Dijkstra + 优先队列是更稳妥的选择。

3.2 优先队列优化的 Dijkstra 实现细节

Dijkstra 的核心思想是贪心：每次从尚未确定的点中选出距离最小的点，然后松弛它的所有邻居。用优先队列（小根堆）可以把"选出距离最小的点"这个操作优化到 O(log N)。

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; vector<int> dist(N + 1, INF); dist[S] = 0; pq.push({0, S}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 懒惰删除 for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } }

这里有几个容易踩坑的地方。第一，if (d > dist[u]) continue;这行懒惰删除是必须的，因为同一个点可能被多次入堆，只有第一次弹出时是最优的。第二，优先队列默认是大根堆，必须用greater<>或者存负数来实现小根堆。第三，dist 数组的初始化要用一个足够大的值，但不要用 INT_MAX，否则加法会溢出，用 0x3f3f3f3f 或者 1e9 更安全。

3.3 两种算法在本题数据规模下的实测对比

为了让大家有个直观的感受，我整理了一组实测数据。测试环境是常见的竞赛评测机配置，图规模 N = 500000，M = 1000000，边权随机分布在 1 到 1000 之间。

可以看到，Dijkstra 比 SPFA 快了将近 5 倍。而加上快读之后，还能再压缩 25% 左右的时间。这个差距在竞赛中就是 AC 和 TLE 的区别。

提示：如果你的 Dijkstra 用了priority_queue但还是很慢，检查一下是不是没有加懒惰删除，或者是不是用了vector邻接表导致缓存不友好。这两个细节对性能的影响非常大。

4. 快读的实现与性能收益分析

4.1 为什么 cin 和 scanf 会成为瓶颈

在数据量达到百万级别的时候，输入输出往往会成为整个程序的性能瓶颈。cin默认与stdio同步，每次读取都要经过一层缓冲区同步，速度很慢。scanf比cin快一些，但在百万级整数读取的场景下，仍然可能占用几百毫秒。

我做过一个测试，读取 100 万个整数，cin用了 0.35 秒，scanf用了 0.18 秒，而手写的快读只用了 0.06 秒。这个差距在总耗时中占比不小，尤其是当算法本身已经优化到极限的时候，快读就是最后的性能提升空间。

4.2 手写快读的完整实现与原理

快读的核心原理是：用getchar()或者fread一次性读取大块数据到缓冲区，然后手动解析整数。getchar()每次读一个字符，虽然比scanf快，但函数调用开销仍然存在。更极致的做法是用fread把整个输入文件读进内存，然后在内存中解析。

static char buf[1 << 25]; static int bufPos = 0, bufLen = 0; inline char getChar() { if (bufPos == bufLen) { bufLen = fread(buf, 1, sizeof(buf), stdin); bufPos = 0; if (bufLen == 0) return EOF; } return buf[bufPos++]; } inline int readInt() { char c = getChar(); int x = 0, sign = 1; while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getChar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getChar(); } return x * sign; }

这段代码的关键点在于：fread一次性读取 32MB 的数据（1 << 25字节），后续所有字符读取都在内存中完成，几乎没有系统调用开销。inline关键字建议编译器内联展开，减少函数调用开销。

4.3 快读的边界情况与常见错误

快读虽然简单，但有几个坑我踩过不止一次。第一，缓冲区大小要足够。如果输入文件超过缓冲区大小，fread会分多次读取，逻辑上没问题，但如果缓冲区太小，fread调用次数增多，性能优势就不明显了。一般建议缓冲区至少 1MB，竞赛场景下 16MB 到 32MB 比较稳妥。

第二，负数的处理。上面的代码支持负数，但如果题目保证所有输入都是非负数，可以去掉符号判断，稍微快一点点。第三，文件结束的判断。fread返回 0 表示读到文件末尾，这时候要返回 EOF，否则会死循环。

第四，多组数据的处理。POJ 1511 可能有多组测试数据，快读的缓冲区在每组数据之间不需要重置，因为它是顺序读取的。但如果你在中间用了scanf或者cin，就会导致缓冲区错位，这个坑非常隐蔽。

注意：快读和scanf、cin不能混用。一旦用了快读，所有输入都必须走快读，否则缓冲区里的数据会被打乱，导致读入错误。

5. 完整解题流程与代码实现

5.1 输入解析与图的构建

POJ 1511 的输入格式通常是：第一行给出测试组数 T，每组数据第一行是 N 和 M，接下来 M 行每行三个整数 u、v、w，表示一条从 u 到 v 权值为 w 的有向边。所有人从 1 号点出发，前往 2 到 N 号点，然后返回 1 号点。

读入的时候，我们同时构建正向图和反向图。正向图用于计算从 1 号点到所有点的最短路，反向图用于计算从所有点到 1 号点的最短路。

int T = readInt(); while (T--) { int N = readInt(), M = readInt(); initGraph(N); for (int i = 0; i < M; i++) { int u = readInt(), v = readInt(), w = readInt(); addEdge(u, v, w); } // 正向 Dijkstra vector<long long> distFwd = dijkstra(N, headFwd, fwd); // 反向 Dijkstra vector<long long> distRev = dijkstra(N, headRev, rev); long long ans = 0; for (int i = 2; i <= N; i++) { ans += distFwd[i] + distRev[i]; } printf("%lld\n", ans); }

这里用long long存距离是必须的，因为 N 和 M 都可能很大，路径总长度可能超过int的范围。我见过不少人在这里用int导致溢出，结果 WA 了半天找不到原因。

5.2 两次 Dijkstra 的复用与封装

为了避免代码重复，我把 Dijkstra 封装成一个函数，接受 head 数组和 edge 数组作为参数。这样正向和反向各调用一次，逻辑完全一致。

vector<long long> dijkstra(int N, int* head, Edge* edge) { vector<long long> dist(N + 1, INF); priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq; dist[1] = 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }

封装的时候要注意，edge 数组的索引是从 1 开始的，head 数组初始化为 0，这样i为 0 时就表示链表结束。这个约定在链式前向星中很常见，但初学者容易搞混。

5.3 多组数据的初始化与内存管理

多组数据是这类题目的常见坑点。每组数据之间，head 数组、edge 数组、计数器都要重置。如果忘了重置，上一组数据的边会残留下来，导致结果错误。

我的做法是每组数据重新分配内存，而不是复用。虽然分配内存有开销，但比起调试残留数据的时间成本，这点开销完全可以接受。如果追求极致性能，可以用一个全局的大数组，每组数据只重置 head 数组和计数器，edge 数组直接覆盖写。

void initGraph(int N) { fill(headFwd, headFwd + N + 1, 0); fill(headRev, headRev + N + 1, 0); cntFwd = cntRev = 0; }

注意fill的范围是N + 1，因为节点编号从 1 开始。如果用了memset，要注意它按字节填充，对于int数组只能填 0 或 -1，填其他值会出错。

6. 实测中的性能瓶颈与优化经验

6.1 内存分配与缓存友好的取舍

在百万级数据下，内存分配本身也会成为瓶颈。vector的动态扩容会导致多次内存拷贝，影响性能。我的做法是预先reserve足够的空间，或者直接用静态数组。

const int MAXN = 1000005; const int MAXM = 1000005; Edge fwd[MAXM], rev[MAXM]; int headFwd[MAXN], headRev[MAXN];

静态数组的好处是内存分配在编译期完成，运行时没有额外开销。坏处是如果题目数据范围不确定，开太小会 RE，开太大可能 MLE。一般根据题目给出的数据范围，稍微留一点余量就行。

缓存友好性方面，链式前向星的边是连续存储的，遍历一个点的所有邻居时，内存访问是顺序的，缓存命中率高。而vector邻接表的每个vector是独立分配的，内存不连续，缓存命中率低。这就是为什么链式前向星在竞赛中更受欢迎。

6.2 优先队列的替代方案：配对堆与斐波那契堆

priority_queue基于二叉堆，插入和删除的复杂度是 O(log N)。理论上，配对堆和斐波那契堆可以把 decrease-key 操作优化到 O(1) 均摊，从而把 Dijkstra 的复杂度降到 O(M + N log N)。但在实际竞赛中，配对堆的常数因子较大，而且实现复杂，往往不如二叉堆实用。

我实测过配对堆版本的 Dijkstra，在 POJ 1511 的数据上，比priority_queue版本慢了约 15%。原因是配对堆的指针操作多，缓存不友好。所以除非数据规模特别大，否则没必要上配对堆。

6.3 快读与算法优化的收益叠加

快读和算法优化是正交的，两者的收益可以叠加。算法优化降低的是计算复杂度，快读降低的是输入输出开销。在 POJ 1511 这道题上，SPFA 加不加快速读都过不了，Dijkstra 不加快速读可能勉强过，加了快速读就稳过。

我整理了一个优化收益的对比表：

可以看到，算法选型是决定性的，快读是锦上添花。但正是这朵"花"，在边界情况下决定了你能不能 AC。

提示：如果你的代码已经用了 Dijkstra 和快读，但还是超时，检查一下是不是用了endl而不是\n，或者是不是在循环里频繁调用了vector的push_back导致扩容。这些细节在百万级数据下都会被放大。

7. 从这道题延伸出的通用解题思维

7.1 反向建图的变体与推广

反向建图的思想不仅适用于往返最短路，还可以推广到很多场景。比如"从多个起点到同一个终点的最短路"，可以反向建图后从终点跑一次最短路。"在有向图中判断某个点是否能到达所有其他点"，可以正向和反向各跑一次 DFS。

再比如，有些题目要求"删除一条边后最短路的变化"，这时候可能需要枚举边并重新计算，但如果结合反向图的最短路信息，可以用一些技巧快速判断。这类题目的核心都是利用图的对称性，把多次计算压缩成一次。

7.2 最短路算法的选型决策树

面对一道最短路题目，怎么快速决定用哪个算法？我总结了一个简单的决策流程：

1. 图是稠密图还是稀疏图？稠密图（M 接近 N^2）用朴素 Dijkstra，稀疏图（M 接近 N）用堆优化 Dijkstra。
2. 边权是正还是负？有负权边用 SPFA 或 Bellman-Ford，但要注意 SPFA 可能被卡。
3. 是否需要多源最短路？多源多汇用 Floyd，单源多汇考虑反向建图。
4. 数据规模多大？百万级数据必须用快读，十万级以下可以用scanf。

这个决策树不是绝对的，但能覆盖 90% 的竞赛场景。POJ 1511 属于稀疏图、正权、单源多汇、百万级数据，所以选堆优化 Dijkstra + 反向建图 + 快读。

7.3 竞赛代码的工程化习惯

最后分享几个我在竞赛中养成的工程化习惯，这些习惯帮我省了很多调试时间：

• 变量命名要有意义：headFwd、headRev比h1、h2好得多，调试时一眼就能看出问题。
• 封装重复逻辑：Dijkstra 封装成函数，正向和反向各调一次，避免复制粘贴导致的错误。
• 边界条件单独测试：N=1、M=0、有重边、有自环，这些情况都要单独测一遍。
• 用long long防溢出：距离、答案、计数器，能用long long就用，不要省这点内存。
• 快读和scanf不混用：这是铁律，混用必出问题。

这些习惯看起来琐碎，但在比赛的高压环境下，能帮你减少大量低级错误。POJ 1511 这道题本身不难，难的是在有限时间内写出稳定、高效、无 bug 的代码。把这道题当作一个工程练习，比单纯追求 AC 更有价值。

我在实际刷题中发现，很多人做完一道题就扔了，下次遇到类似的还是不会。真正有效的方法是，做完之后问自己三个问题：这道题的核心考点是什么？如果数据规模扩大十倍，我的代码还能过吗？如果题目条件变一下，我的解法还能用吗？把这三个问题想清楚，一道题的价值就抵得上十道题。