1. 从一道题看最短路径与深度优先搜索的配合逻辑“PTA 7-112 旅游规划”这道题在数据结构与算法的练习里算是非常经典的一道综合题。它表面上是一个旅游路线规划的场景实际上考察的是单源最短路径与多条件约束下的路径选择这两个核心能力。题目大意是给定若干城市和它们之间的公路无向图每条公路有长度和过路费两个权重要求找出一条从出发地到目的地的最短路径如果最短路径不唯一则选择其中过路费最少的那条。我第一次做这道题的时候第一反应是直接上 Dijkstra因为“最短路径”四个字太显眼了。但真正动手写的时候才发现这题并不是单纯求一个最短距离而是要在距离相等的情况下比较费用这就需要在松弛操作里同时维护两个维度的信息。更麻烦的是题目还要求输出最短路径的条数这就不是简单的最短路计数了因为“最短”的定义被扩展成了“距离优先、费用次之”的双关键字排序。所以这道题的核心难点可以拆成三层第一层是图论建模把城市和公路抽象成带权无向图第二层是双关键字最短路的松弛逻辑第三层是最短路径条数的统计。很多人卡在第三层因为路径条数的统计在双关键字条件下需要特别小心不能简单地在距离更新时加一还要考虑距离相同但费用不同的情况。我后来复盘的时候意识到这道题其实是一个很好的模板题它把 Dijkstra 的变体、路径计数、多条件排序这几个知识点串在了一起。如果你能把这道题吃透以后遇到类似“最短路径不唯一时按第二关键字选择”的题目基本都能套用同样的框架。下面我就按照自己实际做题和调试的过程把这道题的完整思路、代码实现和踩坑经验整理出来。2. 题目核心需求拆解与图论建模2.1 输入输出格式的准确理解先看输入格式。题目通常会给出一行四个整数N、M、S、D分别表示城市数量、公路数量、出发地编号、目的地编号。城市编号从 0 到 N-1。接下来 M 行每行四个整数城市1、城市2、公路长度、过路费。注意这里是无向图所以每条边要存两个方向。输出要求一般是三个数最短路径的总长度、最短路径的总费用、最短路径的条数。有些版本的题目还会要求输出具体路径但 7-112 这个编号对应的版本通常只要求输出这三个统计量。我一开始看题的时候漏掉了一个细节题目说的是“如果最短路径不唯一则选择过路费最少的那条”这意味着我们需要在 Dijkstra 的过程中同时比较距离和费用。如果只比较距离那么当两条路径距离相同时我们无法判断哪条更优。所以距离和费用必须作为一个整体来比较。2.2 为什么选择 Dijkstra 而不是其他算法这道题的所有边权都是非负的公路长度和过路费都是正数所以 Dijkstra 是天然的选择。有人可能会问能不能用 Floyd当然可以Floyd 求多源最短路时间复杂度 O(N^3)对于 N 不超过 500 的题目来说也能过。但 Floyd 的问题在于它不方便统计路径条数而且双关键字的比较在 Floyd 的三重循环里写起来很别扭。也有人会想用 DFS 暴力搜索所有路径然后比较。但城市数量稍微大一点DFS 就会超时因为路径数量是指数级的。所以 DFS 在这道题里只能作为暴力对拍的工具不能作为正式解法。我最终选择的是堆优化版的 Dijkstra因为它的时间复杂度是 O(M log N)对于稀疏图非常友好。而且堆优化版本在松弛操作里可以很方便地同时更新距离、费用和路径条数。2.3 双关键字比较规则的数学表达我们需要定义一个比较函数对于两条到达同一个节点的路径 A 和 B如果 A 的距离小于 B 的距离则 A 更优如果距离相等则比较费用费用小的更优如果距离和费用都相等则两条路径等价路径条数要累加。用数学语言描述就是路径 A 优于路径 B 当且仅当 (dist[A] dist[B]) 或 (dist[A] dist[B] 且 cost[A] cost[B])。这个比较规则必须贯穿整个 Dijkstra 的松弛过程不能只在最后比较。我见过有人只在最后输出的时候比较费用中间松弛只按距离来这样会导致中间状态丢失了费用信息最终选出来的路径可能不是费用最小的。这是一个非常典型的错误后面我会在常见问题里详细说。3. 核心数据结构与算法细节实现3.1 邻接表的构建与边权存储因为是无向图每条边要存两次。我习惯用 vector 套结构体的方式来做邻接表struct Edge { int to; int length; int cost; }; vectorEdge adj[MAXN];这样对于每条输入边 u、v、len、c我们执行adj[u].push_back({v, len, c}); adj[v].push_back({u, len, c});用邻接表而不是邻接矩阵的原因是城市数量可能达到几百甚至上千邻接矩阵的空间是 O(N^2)而邻接表的空间是 O(M)对于稀疏图来说邻接表更省空间遍历邻居也更快。这里有一个小细节如果两个城市之间有多条公路邻接表会保留所有边Dijkstra 在松弛时会自动选择更优的那条。但有些题目会保证任意两个城市之间最多只有一条公路这时候就不需要特殊处理。我一般会在读入的时候不做去重因为 Dijkstra 本身能处理重边。3.2 距离、费用、路径条数三个数组的初始化我们需要三个数组dist[i]从起点到节点 i 的最短距离cost[i]在最短距离前提下的最小费用cnt[i]从起点到节点 i 的最短路径条数初始化的时候所有 dist 设为无穷大cost 也设为无穷大cnt 全部设为 0。起点的 dist 设为 0cost 设为 0cnt 设为 1。这里有一个容易忽略的点起点的 cnt 必须是 1而不是 0。因为从起点到起点本身有一条长度为 0 的路径这条路径是存在的。如果设为 0后面所有路径计数都会是 0。const int INF 0x3f3f3f3f; int dist[MAXN], cost[MAXN], cnt[MAXN]; fill(dist, dist N, INF); fill(cost, cost N, INF); fill(cnt, cnt N, 0); dist[S] 0; cost[S] 0; cnt[S] 1;3.3 优先队列的排序规则设计堆优化 Dijkstra 需要一个优先队列队列里存的是节点编号和当前的距离。但因为我们有双关键字队列的排序规则应该以距离为主费用为辅。不过实际上我们只需要在队列里存距离和节点编号因为费用是在松弛时比较的不需要作为队列的排序依据。struct Node { int u; int d; bool operator(const Node other) const { return d other.d; // 小根堆 } }; priority_queueNode pq; pq.push({S, 0});有人会问为什么不在队列里也存费用因为队列的作用是每次取出当前距离最小的节点费用只在距离相等时才有比较意义。如果两个节点距离相同但费用不同它们谁先出队其实不影响最终结果因为松弛操作会正确处理。所以队列只需要按距离排序即可。3.4 松弛操作中的双关键字更新逻辑这是整道题最核心的部分。对于当前节点 u遍历它的所有邻居 v设边权为 len 和 c。新的距离nd dist[u] len新的费用nc cost[u] c。然后分三种情况第一种nd dist[v]说明找到了一条更短的路径直接更新 dist[v]、cost[v]并且把 cnt[v] 设为 cnt[u]因为到达 u 的每一条最短路径都可以延伸到 v。同时把 v 压入队列。第二种nd dist[v]说明找到了一条距离相同的路径。这时候比较费用如果nc cost[v]说明这条路径费用更小更新 cost[v]并且 cnt[v] 要重新设为 cnt[u]因为之前统计的路径虽然距离相同但费用更大不再是最优路径。如果nc cost[v]说明找到了一条完全等价的路径cnt[v] 累加 cnt[u]。第三种nd dist[v]直接忽略。用代码表示就是for (auto e : adj[u]) { int v e.to; int nd dist[u] e.length; int nc cost[u] e.cost; if (nd dist[v]) { dist[v] nd; cost[v] nc; cnt[v] cnt[u]; pq.push({v, nd}); } else if (nd dist[v]) { if (nc cost[v]) { cost[v] nc; cnt[v] cnt[u]; pq.push({v, nd}); } else if (nc cost[v]) { cnt[v] cnt[u]; } } }注意第二种情况里当nc cost[v]时我们也要把 v 压入队列。因为费用更新了虽然距离没变但后续通过 v 到达其他节点的费用可能会变小所以需要重新松弛。这是一个很容易漏掉的细节我当初就因为这个点卡了很久。4. 完整代码实现与逐行注释4.1 完整 C 代码#include bits/stdc.h using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; struct Edge { int to, length, cost; }; struct Node { int u, d; bool operator(const Node other) const { return d other.d; } }; vectorEdge adj[MAXN]; int dist[MAXN], cost[MAXN], cnt[MAXN]; bool visited[MAXN]; int main() { int N, M, S, D; cin N M S D; for (int i 0; i M; i) { int u, v, len, c; cin u v len c; adj[u].push_back({v, len, c}); adj[v].push_back({u, len, c}); } fill(dist, dist N, INF); fill(cost, cost N, INF); fill(cnt, cnt N, 0); fill(visited, visited N, false); dist[S] 0; cost[S] 0; cnt[S] 1; priority_queueNode pq; pq.push({S, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.u; if (visited[u]) continue; visited[u] true; for (auto e : adj[u]) { int v e.to; int nd dist[u] e.length; int nc cost[u] e.cost; if (nd dist[v]) { dist[v] nd; cost[v] nc; cnt[v] cnt[u]; pq.push({v, nd}); } else if (nd dist[v]) { if (nc cost[v]) { cost[v] nc; cnt[v] cnt[u]; pq.push({v, nd}); } else if (nc cost[v]) { cnt[v] cnt[u]; } } } } cout dist[D] cost[D] cnt[D] endl; return 0; }4.2 关键代码段的逻辑说明visited数组的作用是防止同一个节点被重复处理。在堆优化 Dijkstra 中一个节点可能被多次压入队列但只有第一次出队时才是最优的。所以出队时如果visited[u]为真直接跳过。cnt[v] cnt[u]这一句在距离更新和费用更新时都要执行因为到达 v 的最优路径完全依赖于到达 u 的最优路径。如果到达 u 的最优路径有 cnt[u] 条那么每一条都可以延伸到 v所以到达 v 的最优路径也是 cnt[u] 条。cnt[v] cnt[u]只在距离和费用都相等时执行因为这时候到达 v 的最优路径又多了一批这批路径的数量等于到达 u 的最优路径数量。4.3 时间复杂度与空间复杂度分析时间复杂度每个节点最多出队一次每次出队遍历所有邻居。总边数是 M所以遍历邻居的总次数是 2M。每次压入队列的操作是 O(log M)。所以总时间复杂度是 O((N M) log N)对于 N 和 M 都在 500 以内的题目来说运行时间在毫秒级别。空间复杂度邻接表存储 2M 条边三个数组各 N 个元素优先队列最多 N 个元素。总空间复杂度是 O(N M)。5. 常见错误与调试经验实录5.1 路径条数统计的典型错误我见过最多的错误就是在距离更新时把cnt[v] cnt[u]写成了cnt[v] 1。这样会导致所有节点的路径条数都是 1最终输出也是 1。正确的做法是继承前驱节点的路径条数。还有一个错误是在费用更新时忘记重置 cnt[v]。比如先按距离更新了 cnt[v] cnt[u]后来发现费用更小这时候 cnt[v] 应该重新设为 cnt[u]而不是累加。因为之前统计的路径虽然距离相同但费用更大已经不再是最优路径了。5.2 优先队列中节点重复入队的问题在双关键字更新中当nd dist[v]且nc cost[v]时我们也会把 v 压入队列。这时候 v 可能在队列里已经存在了但没关系因为 visited 数组会保证它只被处理一次。不过要注意如果 v 已经出队并被标记为 visited那么后续的更新其实不会影响最终结果因为 Dijkstra 的性质保证了第一次出队时就是最优的。但有一种特殊情况如果我们在 v 出队之后才发现一条费用更小的路径这时候 v 已经 visited 了不会再被处理。这会不会导致错误答案是不会因为 Dijkstra 的贪心性质保证了当 v 出队时dist[v] 已经是最小的而费用是在距离相等时比较的如果存在另一条距离相同但费用更小的路径那么这条路径的前驱节点一定会在 v 之前出队所以 v 在出队之前就已经被更新了。5.3 无向图边存储的方向问题无向图每条边要存两次这个大家都知道。但有时候会忘记在输入的时候存两次导致图变成有向图结果只能沿一个方向走。我建议在读入的时候直接写两行 push_back不要想着后面再补。5.4 常见问题速查表问题现象可能原因解决方法输出路径条数为 0起点 cnt 初始化为 0起点 cnt 设为 1输出路径条数为 1更新时 cnt[v] 设为 1改为 cnt[v] cnt[u]费用不是最小只在最后比较费用在松弛时同时比较距离和费用程序超时用了 DFS 暴力改用堆优化 Dijkstra结果偏大无向图只存了一个方向每条边存两次费用更新后结果不对费用更新时忘记压入队列费用更新后也要 push6. DFS 暴力解法与对拍验证6.1 DFS 暴力搜索的实现虽然 DFS 不能作为正式解法但写一个暴力版本用来对拍是非常有用的。DFS 的思路很简单从起点出发遍历所有可能的路径记录到达终点时的距离、费用和路径条数。如果当前路径的距离小于已知最优距离更新如果距离相等但费用更小更新如果距离和费用都相等路径条数加一。void dfs(int u, int d, int c) { if (u D) { if (d bestDist) { bestDist d; bestCost c; bestCnt 1; } else if (d bestDist) { if (c bestCost) { bestCost c; bestCnt 1; } else if (c bestCost) { bestCnt; } } return; } for (auto e : adj[u]) { if (!visited[e.to]) { visited[e.to] true; dfs(e.to, d e.length, c e.cost); visited[e.to] false; } } }DFS 的时间复杂度是指数级的只能处理 N 很小的情况。我一般用 N 10 的随机数据来对拍验证 Dijkstra 的正确性。6.2 随机数据生成与对拍脚本对拍的时候我用一个简单的随机数据生成器srand(time(0)); int N rand() % 8 2; int M rand() % (N * (N - 1) / 2) 1; int S rand() % N; int D rand() % N; while (D S) D rand() % N; cout N M S D endl; // 随机生成 M 条边...然后写一个 shell 脚本循环运行两个程序比较输出是否一致。如果发现不一致就把那组数据保存下来手动分析。6.3 对拍中发现的边界情况对拍的时候我发现了一个边界情况当起点和终点是同一个城市时最短距离是 0费用是 0路径条数是 1。但有些人的代码会输出 0 条路径因为他们在初始化的时候把起点的 cnt 设为了 0。这个边界情况在正式测试数据里可能不会出现但写代码的时候最好还是处理一下。还有一个情况是当图中存在多条完全相同的边时路径条数会翻倍。比如从 A 到 B 有两条长度和费用都相同的公路那么从 A 到 B 的最短路径条数应该是 2。Dijkstra 在处理重边时如果两条边都被遍历到cnt 会正确累加。但如果用邻接矩阵重边会被覆盖导致路径条数少算。所以这道题最好用邻接表。7. 从这道题延伸出的通用解题框架7.1 双关键字最短路的通用模板这道题的解法可以抽象成一个通用模板当最短路径有多个评价维度时定义一个比较函数在松弛操作中按照优先级依次比较。优先级高的维度先比较相等时再比较优先级低的维度。路径条数的统计规则是当找到更优路径时继承前驱的条数当找到等价路径时累加前驱的条数。这个模板可以扩展到三关键字甚至更多关键字的情况。比如有些题目要求距离最短、费用最少、时间最少那就依次比较距离、费用、时间。代码结构是一样的只是比较的层数变多了。7.2 路径计数类问题的注意事项路径计数类问题有一个通用的坑当图中存在环时路径数量可能是无限的。但这道题的所有边权都是正数所以最短路径一定不会包含环路径数量是有限的。如果边权允许为 0那么就需要特别处理因为 0 权环会导致路径数量无限。不过 PTA 的这道题没有这个问题。另外路径条数可能会很大超出 int 的范围。但这道题的 N 不超过 500路径条数最多是指数级的但实际上由于图的结构限制路径条数不会太大。如果担心溢出可以用 long long。我一般直接用 int因为 PTA 的测试数据不会故意卡这个。7.3 类似题目的变体与应对策略这道题有几个常见的变体第一个变体是要求输出具体路径。这时候需要额外维护一个 pre 数组记录每个节点的前驱。在更新距离或费用时同时更新 pre。最后从终点回溯到起点输出路径。第二个变体是要求输出所有最短路径。这时候就不能只统计条数了需要用 DFS 从终点回溯找出所有满足条件的路径。这种题一般 N 很小否则输出量会爆炸。第三个变体是边权可能为负数。这时候 Dijkstra 就不能用了需要用 Bellman-Ford 或 SPFA。但 PTA 的这道题边权都是正数所以 Dijkstra 是安全的。我在实际做题的时候一般会先判断边权是否非负如果是优先用 Dijkstra如果有负权再考虑其他算法。这道题明显属于前者。8. 个人实操心得与效率提升建议8.1 代码模板化与快速复用这道题的代码结构非常固定我建议把它整理成一个模板以后遇到类似的双关键字最短路问题可以直接套用。模板的核心就是三个数组、一个优先队列、一个松弛循环。把比较逻辑抽成一个函数这样修改比较规则的时候只需要改一个地方。我自己的模板里比较函数是这样的bool better(int d1, int c1, int d2, int c2) { if (d1 ! d2) return d1 d2; return c1 c2; }然后在松弛的时候调用这个函数代码会清晰很多。8.2 调试技巧打印中间状态Dijkstra 的调试比较麻烦因为中间状态很多。我一般会在松弛的时候打印关键信息比如当前节点、邻居节点、新旧距离和费用。这样能快速定位是哪一步更新出了问题。另外我习惯在最后输出之前把 dist、cost、cnt 三个数组都打印出来看看每个节点的状态是否合理。如果某个节点的 cnt 特别大或者特别小就说明统计逻辑可能有问题。8.3 时间分配与做题策略在 PTA 上做这道题的时候我建议先花 5 分钟理清题意确认是双关键字最短路加路径计数。然后用 15 分钟写代码10 分钟调试。如果卡住了不要死磕先写一个 DFS 暴力版本用随机数据对拍往往能快速发现问题。这道题的分值是 25 分属于中等难度。如果能在 30 分钟内 AC说明对 Dijkstra 的掌握已经比较扎实了。如果超过 45 分钟还没过建议回头复习一下最短路的基础知识特别是松弛操作和优先队列的使用。8.4 从做题到工程实践的映射虽然这是一道算法题但它背后的思想在工程实践中也很常见。比如在导航软件里规划路线时不仅要考虑距离最短还要考虑拥堵情况、收费多少、红绿灯数量等多个因素。这时候就需要多关键字的最短路径算法。再比如在网络路由中选择路径时不仅要考虑跳数最少还要考虑带宽、延迟、丢包率等指标。这些场景都可以用类似的框架来解决。所以这道题不仅仅是一道考试题它其实是一个简化版的工程问题。把这道题吃透对理解实际系统中的路径规划问题很有帮助。我在实际工作中遇到过一个类似的需求需要在一个物流网络中找出一条运输成本最低且时间最短的路径当时就是用了这道题的思路把成本和时间的优先级定义清楚然后用 Dijkstra 的变体来解决。最后再分享一个小技巧如果题目要求输出的路径条数可能很大可以在每次累加的时候取模。但 PTA 的这道题没有要求取模所以直接输出原值即可。如果担心溢出用 long long 更保险。