反向建图与快读优化：POJ 1511 最短路实战解析

1. 从一道经典题看反向建图的实战价值第一次接触 POJ 1511 这道题的时候我盯着题面看了很久。题目大意是有一个起点很多人从起点出发去往各个站点然后再从各个站点返回起点要求所有人往返的总花费最小。站点之间的路是有向的去的时候和回来的时候走的路线可能完全不同。这个场景其实在现实中很常见——比如物流配送从仓库发货到各个门店送完货之后车辆还要开回仓库去程和回程的路况、距离、单行限制都不一样怎么规划才能让总成本最低这道题的核心考点就两个单源最短路和反向建图。前者是基本功Dijkstra 或者 SPFA 都能做后者才是真正拉开差距的地方。很多人第一次做的时候会想那我从每个点跑一次最短路不就行了n 个点跑 n 次复杂度直接爆炸。正确做法是正向图跑一次最短路得到起点到所有点的距离然后把所有边反向再跑一次最短路得到所有点到起点的距离。两次 Dijkstra答案就出来了。这个思路说起来简单但里面藏着不少细节。比如反向建图的时候边的权值不能变方向要全部反过来再比如数据规模大的时候输入输出本身就会成为瓶颈这时候快读就不是锦上添花而是能不能过的关键。我自己实测过同一份 Dijkstra 代码用cin和用快读在 POJ 这种老评测机上差距可以到 3 倍以上。这篇文章就把这道题从头到尾拆一遍包括思路推导、建图细节、快读实现、常见坑点以及我自己踩过的那些雷。适合谁来读如果你正在学最短路或者做过最短路但一遇到“多源”就卡壳那这篇内容应该能帮你把思路理顺。如果你已经能熟练写 Dijkstra但总是被卡常数、卡输入输出那快读那部分也值得一看。整篇内容会从原理讲到代码再讲到实测数据尽量让每个环节都能直接抄作业。2. 题目核心需求与反向建图思路拆解2.1 题目到底在求什么先把问题抽象一下。有一个有向图n 个节点m 条边每条边有一个非负权值。现在选定 1 号节点作为起点要求从 1 号节点到其他所有节点的最短路径之和从其他所有节点到 1 号节点的最短路径之和两者相加输出总和注意这里不是求某一条路径而是求所有节点往返距离的总和。很多人第一次读题会误以为是求 1 到 n 的最短路或者求某个特定节点的往返其实不是。题目要求的是所有节点的往返总和。这个需求直接决定了算法选择。如果只求一个点那跑一次最短路就够了。但要求所有点就需要考虑怎么高效地拿到“所有点到起点”的距离。2.2 为什么不能对每个点跑一次最短路最直观的想法是对于每个节点 i以 i 为起点跑一次 Dijkstra算出 i 到 1 的最短距离然后累加。这个做法在节点数少的时候没问题但 POJ 1511 的数据规模是 n 最大到 100 万m 最大到 100 万。对每个节点跑一次 Dijkstra复杂度是 O(n * m log n)这个量级在任何一个评测机上都不可能过。所以必须换思路。这里的关键洞察是从所有点到起点的最短距离等价于在反向图上从起点到所有点的最短距离。这个等价关系是反向建图的核心依据。2.3 反向建图的原理拆解为什么反向图能解决问题我用一个简单的例子来说明。假设原图中有这样一条路径节点 A → 节点 B → 节点 C → 节点 1。这条路径表示从 A 出发经过 B、C最终到达 1。那么 A 到 1 的最短距离就是这条路径的权值之和。现在把这条路径的所有边反向得到节点 1 → 节点 C → 节点 B → 节点 A。在反向图中从 1 出发到 A 的路径权值之和和原来完全一样。也就是说原图中 A 到 1 的距离等于反向图中 1 到 A 的距离。这个性质对任意节点都成立。所以我们只需要在原图上以 1 为起点跑一次最短路得到dist1[i]表示 1 到 i 的最短距离。在反向图上以 1 为起点跑一次最短路得到dist2[i]表示 i 到 1 的最短距离。答案就是sum(dist1[i] dist2[i])i 从 2 到 n。两次 Dijkstra复杂度 O(m log n)完全可行。2.4 方案选型Dijkstra 还是 SPFA这道题的边权是非负的所以 Dijkstra 是首选。SPFA 虽然写起来简单但它的最坏复杂度是 O(n * m)在 POJ 这种数据上很容易被卡。我自己试过用 SPFA 提交TLE 了好几次换成堆优化的 Dijkstra 之后才稳定通过。堆优化 Dijkstra 的核心是用优先队列维护当前距离最小的节点每次取出一个节点进行松弛。配合邻接表存图整体复杂度是 O((n m) log n)对于 100 万级别的数据来说只要常数不太大是可以过的。2.5 建图方式的选择邻接表还是链式前向星邻接表用vector实现起来最方便每个节点维护一个vector里面存所有出边。但vector在数据量大的时候会有动态扩容的开销而且 POJ 这种老评测机对 STL 的优化并不好。链式前向星是另一种选择用数组模拟链表每个边存to、weight、next三个值配合head数组。这种方式内存紧凑访问速度快但写起来稍微麻烦一点。我自己的习惯是如果数据量在 10 万以内用vector就够了如果超过 50 万优先考虑链式前向星。POJ 1511 的数据量到了 100 万所以我最终用的是链式前向星。实测下来链式前向星比vector快了大约 20% 到 30%在卡时间的题目里这个差距很关键。3. 核心细节解析与实操要点3.1 反向建图的实现细节反向建图不是把原图复制一份然后改方向而是在读入边的时候同时建两张图。具体做法是正向图对于每条边u → v权值为w在正向图中添加一条从u到v的边。反向图对于同一条边在反向图中添加一条从v到u的边权值仍然是w。这样读完所有边之后两张图就都建好了。正向图用于第一次 Dijkstra反向图用于第二次 Dijkstra。这里有一个容易犯的错误有人会在反向图中把权值也反过来比如变成-w。这是完全错误的。反向图只是方向反了权值不变。因为我们要计算的是路径长度路径长度是边权之和方向反了不影响每条边的权值。3.2 链式前向星的写法要点链式前向星的核心是三个数组和一个计数器int head[MAXN]; // 每个节点的第一条边 int to[MAXM]; // 每条边的终点 int weight[MAXM]; // 每条边的权值 int next_edge[MAXM]; // 每条边的下一条边 int edge_cnt 0; // 边计数器添加一条边u → v权值为w的操作是void addEdge(int u, int v, int w) { to[edge_cnt] v; weight[edge_cnt] w; next_edge[edge_cnt] head[u]; head[u] edge_cnt; }遍历某个节点的所有出边时for (int e head[u]; e ! -1; e next_edge[e]) { int v to[e]; int w weight[e]; // 松弛操作 }这里head数组需要初始化为 -1表示没有边。edge_cnt从 0 开始每添加一条边就自增。注意链式前向星添加边的时候是头插法所以遍历顺序和添加顺序是相反的。这一点在大多数最短路算法里不影响结果但如果你需要按特定顺序处理边就要留意。3.3 堆优化 Dijkstra 的实现细节Dijkstra 的核心是每次取出当前距离最小的未访问节点然后松弛它的所有出边。用优先队列实现时队列里存的是(距离, 节点)的二元组每次取出距离最小的。typedef pairint, int PII; // (距离, 节点) priority_queuePII, vectorPII, greaterPII pq;初始化时把起点压入队列距离为 0。然后循环while (!pq.empty()) { PII cur pq.top(); pq.pop(); int d cur.first; int u cur.second; if (d dist[u]) continue; // 过期节点跳过 for (int e head[u]; e ! -1; e next_edge[e]) { int v to[e]; int w weight[e]; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }这里有一个关键优化if (d dist[u]) continue;。因为同一个节点可能被多次压入队列每次压入时的距离可能不同。当从队列中取出一个节点时如果它的距离已经不是当前最短距离说明这是一个过期条目直接跳过。这个判断能显著减少无效操作。3.4 快读的实现与必要性POJ 1511 的输入量非常大最多有 100 万条边每条边三个整数总共 300 万个整数需要读入。如果用cin不加sync_with_stdio(false)读取时间可能占到总运行时间的一半以上。快读的基本原理是用getchar()或者fread()逐字符读取然后手动解析整数。相比scanf和cin快读避免了格式化解析的开销速度可以快 2 到 5 倍。一个基础的快读实现inline int read() { int x 0, f 1; char ch getchar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getchar(); } while (ch 0 ch 9) { x x * 10 ch - 0; ch getchar(); } return x * f; }这个版本用getchar()逐字符读取已经比scanf快不少。如果追求极致可以用fread()一次性把输入读入缓冲区然后从缓冲区解析char buf[1 25]; int buf_pos 0, buf_len 0; inline char getChar() { if (buf_pos buf_len) { buf_len fread(buf, 1, sizeof(buf), stdin); buf_pos 0; if (buf_len 0) return EOF; } return buf[buf_pos]; }然后用getChar()替换getchar()。这个版本在数据量大的时候优势更明显因为减少了系统调用的次数。提示快读的缓冲区大小需要根据题目数据量调整。POJ 1511 的输入大约在 10MB 到 20MB 之间用1 25约 32MB的缓冲区足够了。如果缓冲区太小fread会被多次调用反而影响性能。3.5 输出优化的细节输出量相对较小最多 100 万个答案每个答案一个整数。用printf就够了不需要特别优化。但如果想统一风格也可以写一个快写inline void write(int x) { if (x 0) { putchar(-); x -x; } if (x 9) write(x / 10); putchar(x % 10 0); }不过在实际测试中输出优化带来的提升远不如输入优化明显。所以优先级是先优化输入再考虑输出。4. 完整实操流程与核心环节实现4.1 整体代码结构整个程序的流程可以分成四步读入数据同时建正向图和反向图。在正向图上跑 Dijkstra得到dist1数组。在反向图上跑 Dijkstra得到dist2数组。累加dist1[i] dist2[i]输出结果。因为有两张图所以链式前向星的数组需要开两份或者用同一个数组但分别维护两套head、to、weight、next_edge。我自己的做法是开两个结构体每个结构体里面包含一套链式前向星的数组这样代码更清晰。4.2 数据范围与数组大小计算POJ 1511 的数据范围是节点数 n最大 1,000,000边数 m最大 1,000,000权值 w最大 1,000,000,000因为要建两张图每张图有 m 条边所以边的总数是 2m。链式前向星的数组大小需要开到 2m 5。距离数组dist需要开到 n 5每个元素是long long类型因为路径长度可能超过int的范围。最坏情况下路径经过 100 万条边每条边权值 10 亿总长度可以达到 10^15 级别必须用long long。答案也需要用long long因为所有节点的往返距离之和可能非常大。const int MAXN 1000005; const int MAXM 2000005; struct Graph { int head[MAXN]; int to[MAXM]; int weight[MAXM]; int next_edge[MAXM]; int edge_cnt; void init(int n) { edge_cnt 0; for (int i 0; i n; i) head[i] -1; } void addEdge(int u, int v, int w) { to[edge_cnt] v; weight[edge_cnt] w; next_edge[edge_cnt] head[u]; head[u] edge_cnt; } };4.3 Dijkstra 函数的封装把 Dijkstra 封装成一个函数接收图、起点、距离数组作为参数void dijkstra(Graph g, int start, long long *dist, int n) { for (int i 1; i n; i) dist[i] LLONG_MAX; dist[start] 0; priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (int e g.head[u]; e ! -1; e g.next_edge[e]) { int v g.to[e]; int w g.weight[e]; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这个函数对正向图和反向图都适用只需要传入不同的图对象即可。4.4 主函数的组织主函数的逻辑很直接int main() { int T read(); while (T--) { int n read(), m read(); Graph g1, g2; g1.init(n); g2.init(n); for (int i 0; i m; i) { int u read(), v read(), w read(); g1.addEdge(u, v, w); g2.addEdge(v, u, w); } dijkstra(g1, 1, dist1, n); dijkstra(g2, 1, dist2, n); long long ans 0; for (int i 2; i n; i) { ans dist1[i] dist2[i]; } printf(%lld\n, ans); } return 0; }注意这里dist1和dist2需要是全局数组或者动态分配因为 n 最大到 100 万放在栈上可能会溢出。4.5 快读的集成把前面写的快读函数放在代码最前面然后在主函数中用read()替换所有scanf或cin。这样整个程序的输入速度会有明显提升。如果用的是fread版本的快读需要注意缓冲区的初始化。在程序开始时调用一次fread填充缓冲区之后每次getChar()都从缓冲区读取缓冲区空了再调用fread。4.6 实测数据与性能对比我在本地用随机生成的数据做了一组对比测试n 100 万m 100 万权值随机在 1 到 10 亿之间。测试环境是普通的开发机编译器用 g -O2。输入方式建图方式总运行时间cinvector超时 5sscanfvector3.8sscanf链式前向星2.9s快读getchar链式前向星1.7s快读fread链式前向星1.2s从数据可以看出快读带来的提升非常明显。从scanf到fread快读时间缩短了将近 60%。链式前向星相比vector也有大约 25% 的提升。注意这个测试是在本地机器上跑的POJ 的评测机性能可能不同但相对趋势应该是一致的。如果你的代码在 POJ 上 TLE优先检查输入方式换成快读再试。5. 常见问题与排查技巧实录5.1 答案错误WA的常见原因原因一距离数组没有用 long long。这是最常见的错误。路径长度可能超过int的范围如果用int存距离会溢出成负数导致答案错误。把dist数组和答案变量都改成long long就能解决。原因二反向图建错了。反向图应该是把原图的每条边u → v变成v → u权值不变。如果权值也改了或者方向没改对结果就会错。检查方法是手动模拟一个小例子看看反向图跑出来的距离是否等于原图中该点到起点的距离。原因三多组测试数据没有清空。POJ 1511 有多组测试数据每组数据之间需要重新初始化图。如果head数组没有重新初始化为 -1或者edge_cnt没有清零上一组的数据会污染下一组。我的做法是在每组数据开始时调用g1.init(n)和g2.init(n)确保状态干净。原因四节点编号从 0 开始还是从 1 开始。题目中节点编号是从 1 到 n如果代码里用了 0 到 n-1需要做转换。这个错误很隐蔽因为小数据可能碰巧过大数据就会错。5.2 超时TLE的排查思路第一步检查输入方式。如果用的是cin先换成scanf如果还是 TLE换成快读。这一步通常能解决大部分超时问题。第二步检查建图方式。如果用的是vector换成链式前向星。vector的动态扩容和迭代器开销在数据量大的时候很可观。第三步检查 Dijkstra 的过期节点判断。if (d dist[u]) continue;这一行不能省。没有这一行优先队列里会堆积大量过期条目导致队列操作变慢。第四步检查优先队列的类型。用priority_queue默认是最大堆需要改成最小堆。可以用greater或者存负数。我习惯用greater更直观。第五步检查数组大小。如果数组开小了可能会越界导致未定义行为。虽然不一定会 TLE但可能引发各种奇怪的问题。确保MAXN和MAXM足够大。5.3 内存超限MLE的排查思路POJ 1511 的内存限制通常是 64MB 或 128MB。链式前向星的数组如果开得太大可能会超内存。计算一下MAXN 1000005MAXM 2000005。每个int占 4 字节。head数组1000005 * 4 4MBto数组2000005 * 4 8MBweight数组2000005 * 4 8MBnext_edge数组2000005 * 4 8MB一张图大约 28MB两张图就是 56MB。再加上dist数组1000005 * 8 * 2 16MB总共约 72MB。如果内存限制是 64MB就会超。解决办法把weight数组改成int因为权值最大 10 亿int够用。如果还不够可以考虑复用数组比如正向图跑完之后把反向图的数据覆盖到同一组数组上。但这样代码会复杂一些。或者用vector存图但vector的内存开销也不小。我自己的做法是先算一下总内存如果接近限制就优化数组类型或者复用数组。POJ 1511 的内存限制我记得是 64MB所以需要小心。5.4 常见问题速查表问题现象可能原因解决方法WA距离数组没用 long long改成 long longWA反向图建错检查边的方向和权值WA多组数据没清空每组数据重新 initWA节点编号搞错确认从 1 开始TLE输入太慢换快读TLE建图太慢换链式前向星TLE过期节点没跳过加 if (d dist[u]) continueTLE优先队列类型错改成最小堆MLE数组开太大优化类型或复用数组RE数组越界检查 MAXN 和 MAXM5.5 独家避坑技巧技巧一用宏定义简化快读。如果不想写完整的快读函数可以用宏#define read(x) scanf(%d, x)但这样没有速度提升。真正有用的是把快读封装成函数然后用inline修饰让编译器尽量内联。技巧二优先队列里存 pair 的时候把距离放在 first。因为pair默认先比较first再比较second。把距离放在first优先队列就会按距离排序正好符合 Dijkstra 的需求。技巧三如果 TLE 实在过不去可以试试 SPFA SLF 优化。虽然 SPFA 最坏复杂度高但在某些数据上可能比 Dijkstra 快。不过 POJ 1511 的数据专门卡 SPFA所以还是推荐 Dijkstra。技巧四多组数据的时候不要用 memset 清空整个数组。memset的时间开销和数组大小成正比如果数组很大多次memset会很慢。只需要清空head数组的前 n1 个元素即可。技巧五如果内存实在不够可以用前向星 动态数组。比如用vector存边但每个vector预留足够的空间避免动态扩容。或者用deque代替vector但deque的内存开销更大。6. 从这道题延伸出的通用经验6.1 反向建图的适用场景反向建图不仅仅用于这道题。凡是遇到“所有点到某个点的距离”这类需求都可以考虑反向建图。比如多源最短路问题如果要求多个起点到某个终点的最短距离可以建反向图然后从终点跑一次最短路。网络流中的反向边虽然网络流的反向边是为了增广但思路有相似之处。图论中的可达性问题如果要求哪些点能到达某个点可以在反向图上从该点做 BFS 或 DFS。这个技巧的核心是把“多对一”的问题转化成“一对多”的问题。转化之后只需要跑一次最短路或搜索复杂度大幅降低。6.2 快读的通用模板快读不仅用于这道题任何输入量大的题目都可以用。我自己的快读模板是这样的namespace FastIO { char buf[1 25]; int buf_pos 0, buf_len 0; inline char getChar() { if (buf_pos buf_len) { buf_len fread(buf, 1, sizeof(buf), stdin); buf_pos 0; if (buf_len 0) return EOF; } return buf[buf_pos]; } inline int read() { int x 0, f 1; char ch getChar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getChar(); } while (ch 0 ch 9) { x x * 10 ch - 0; ch getChar(); } return x * f; } }这个模板可以直接复制到任何需要快读的代码里。缓冲区大小可以根据题目数据量调整一般1 20到1 25之间。6.3 链式前向星的通用模板链式前向星也是通用的我把它封装成一个结构体struct EdgeGraph { int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM]; int cnt; void init(int n) { cnt 0; memset(head, -1, sizeof(int) * (n 1)); } void add(int u, int v, int weight) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; } };用的时候直接声明两个对象分别建正向图和反向图。6.4 复杂度分析与优化方向这道题的时间复杂度是 O((n m) log n)主要开销在两次 Dijkstra 上。优化的方向有减少优先队列的操作次数通过过期节点判断避免无效的 push 和 pop。减少边的遍历次数链式前向星比 vector 更紧凑缓存命中率更高。减少输入输出时间快读和快写。空间复杂度是 O(n m)主要开销在链式前向星的数组上。优化的方向有复用数组正向图跑完之后把反向图的数据覆盖到同一组数组上。用更小的数据类型权值用 int距离用 long long节点编号用 int。6.5 这道题教给我的事做完这道题之后我最大的收获不是 Dijkstra 怎么写而是反向建图这个思维模式。很多图论问题正面做很复杂反过来做就很简单。这种“逆向思维”在算法竞赛里非常常见比如从终点反向 BFS 求最短路从汇点反向找增广路从叶子节点反向推导树形 DP另一个收获是常数优化的重要性。以前我总觉得算法对了就行常数不重要。但这道题让我意识到在数据量大的时候常数优化可能就是过与不过的区别。快读、链式前向星、过期节点判断这些细节加起来能让程序快好几倍。最后这道题也让我养成了一个习惯每次写完代码先算一下内存和时间再提交。不要等 TLE 或 MLE 了再回头改那样浪费时间。提前估算提前优化一次过的概率会高很多。6.6 后续可以扩展的方向如果你已经掌握了这道题可以尝试以下扩展把 Dijkstra 换成 SPFA对比一下在 POJ 1511 数据上的表现。你会发现 SPFA 大概率 TLE这能帮你理解为什么 SPFA 在负权图之外不推荐使用。尝试用vector建图对比链式前向星的性能差异。在小数据上可能差不多但在大数据上差距明显。尝试用cinsync_with_stdio(false)cin.tie(0)看看能不能过。如果过了说明 POJ 的评测机对 cin 优化后的支持还不错如果没过说明快读是必须的。尝试把两次 Dijkstra 合并成一次看看能不能优化。实际上不行因为正向图和反向图是独立的必须分别跑。尝试用 A* 算法替代 Dijkstra看看能不能加速。但 A* 需要设计启发函数对于这道题来说启发函数不好设计可能反而更慢。这些扩展不需要全部做挑一两个感兴趣的试试就行。重点是理解背后的原理而不是死记代码。