1. 从旅游规划这道题看最短路径问题的双重解法PTA 7-112 旅游规划这道题在数据结构与算法的练习里算是很经典的一道综合题。它表面上是一个旅游路线规划的场景实际上考察的是带权无向图上的最短路径求解而且不是单纯求一条最短路还要在多条最短路中选出花费最少的那一条。这个双重条件的设计是这道题最核心的考点也是很多人第一次做的时候容易翻车的地方。我最初看到这道题的时候第一反应是不就是 Dijkstra 吗结果写完提交发现只过了一半的测试点。后来仔细读题才发现题目要求的是在保证路径总长度最短的前提下如果存在多条长度相同的最短路径要选择过路费总和最小的那条。这就意味着标准的 Dijkstra 模板不能直接套用需要在松弛操作里额外维护一个费用维度。这道题适合谁看如果你正在刷 PTA 的图论专题或者正在准备数据结构考试、算法面试又或者你只是想把 Dijkstra 和 DFS 这两个基础算法真正吃透那这道题是一个非常好的练手素材。它不像纯粹的模板题那样机械也不像复杂的网络流那样劝退刚好卡在一个需要动脑子但又不至于无从下手的难度区间。接下来我会从题目建模、Dijkstra 的双关键字处理、DFS 的暴力验证思路、以及实际编码中踩过的坑这几个角度把这道题彻底拆开讲清楚。文章里给出的代码和思路都是可以直接复现的你照着敲一遍基本就能把这类双条件最短路问题一次性拿下。2. 题目建模把旅游场景翻译成图论语言2.1 城市是点公路是边两个权重分别是什么拿到任何一道图论题第一步永远是把自然语言描述翻译成图的结构。这道题里城市就是图中的顶点vertex两个城市之间的公路就是图中的边edge。题目给的是无向图因为公路是双向通行的。关键在于每条边上有两个权重公路长度这是第一优先级我们要让总长度最小。过路费这是第二优先级在总长度相同的情况下让总费用最小。用邻接矩阵或者邻接表存储的时候每条边需要同时记录这两个值。我一般习惯用结构体或者两个独立的二维数组来存具体看个人习惯。如果用邻接矩阵可以开两个数组dist[i][j]和cost[i][j]分别表示城市 i 到城市 j 的公路长度和过路费。这里有个细节要注意题目中两个城市之间可能有多条公路虽然经典版本通常假设只有一条但保险起见要处理。如果有多条应该保留长度最短的那条如果长度也相同保留费用最小的那条。这个处理逻辑在输入阶段就要做好否则后面 Dijkstra 会出错。2.2 起点、终点和输出要求题目一般会给定起点城市 S 和终点城市 D要求输出最短路径的长度以及该路径上的总过路费。有些版本还会要求输出路径本身但 7-112 这道题通常只要求输出两个数值。输出格式看起来简单但恰恰是这里容易出问题。因为当存在多条最短路径时你输出的费用必须是所有最短路径中最小的那个费用而不是你随便找到的那条路径的费用。这就要求算法在求解过程中必须能够正确地在等长路径中挑最小费用。我见过不少人的代码Dijkstra 只维护了距离数组费用是在最后回溯路径的时候才累加的。这种做法在单条最短路的情况下没问题但一旦有多条等长路径回溯出来的那条未必是费用最小的那条结果就错了。正确的做法是在松弛阶段就把费用作为第二关键字一起更新。2.3 数据规模的判断与存储结构选择在动手写代码之前先看一眼数据范围。PTA 上这类题目的城市数量 N 通常在几百到一千左右边数 M 在几千到几万不等。这个规模下几种存储方式都是可行的存储方式时间复杂度空间复杂度适用场景邻接矩阵O(N²)O(N²)N ≤ 1000 时够用邻接表 优先队列O(M log N)O(N M)稀疏图首选邻接表 普通队列O(N²)O(N M)稠密图也可如果 N 在 500 以内邻接矩阵写起来最省事Dijkstra 直接双重循环找最小值就行代码短、不易出错。如果 N 到了几千甚至上万那就必须上邻接表加优先队列否则会超时。我的建议是先用邻接矩阵把逻辑跑通确认答案正确之后如果超时再改成优先队列版本。这样调试成本最低因为邻接矩阵版本的 Dijkstra 逻辑最直观出错了也容易定位。3. Dijkstra 的双关键字松弛这道题真正的难点3.1 标准 Dijkstra 为什么不够用标准的 Dijkstra 算法维护一个dist[]数组表示从起点到每个点的最短距离。每次从优先队列里取出当前距离最小的点然后遍历它的邻居如果dist[u] w(u,v) dist[v]就更新dist[v]。这个逻辑在处理单一权重的时候是完全正确的因为 Dijkstra 的贪心性质保证了一旦某个点被取出它的最短距离就已经确定不会再被更新。但是这道题有两个权重而且两个权重有优先级之分。距离是第一优先级费用是第二优先级。当dist[u] w(u,v) dist[v]的时候标准 Dijkstra 不会做任何操作但这时候我们其实需要检查通过 u 到达 v 的这条路径费用是不是比当前记录的到 v 的费用更小如果是就要更新费用。这就是这道题的核心改动点松弛条件从单一的小于号变成了小于或者等于但费用更小。3.2 松弛操作的完整逻辑拆解我把松弛部分的逻辑单独拎出来讲因为这里是整道题最容易写错的地方。假设当前从优先队列取出的是节点 u它的最短距离是dist[u]最小费用是cost[u]。现在遍历 u 的邻居 v边 (u,v) 的长度是len费用是fee。那么从 u 到 v 的新路径长度是dist[u] len新费用是cost[u] fee。接下来分三种情况情况一新路径长度小于当前dist[v]这说明找到了一条更短的路不管费用多少都要更新。执行dist[v] dist[u] len; cost[v] cost[u] fee; 把 v 加入优先队列;情况二新路径长度等于当前dist[v]但新费用小于当前cost[v]这说明找到了一条等长但更便宜的路需要更新费用。执行cost[v] cost[u] fee; 把 v 加入优先队列或者只更新费用视实现而定;情况三新路径长度大于当前dist[v]直接忽略因为距离已经不是最优了费用再小也没意义。这里有个容易忽略的点在情况二里距离没有变只是费用变小了。这时候要不要把 v 重新加入优先队列答案是要。因为 v 的费用变了从 v 出发到其他点的路径费用也可能因此变小需要重新松弛 v 的邻居。如果不重新入队就可能漏掉后续的费用更新。不过这里也有一个优化技巧如果用的是优先队列可以只在费用更新时把 v 重新入队然后在取出的时候判断一下当前取出的距离和费用是否和数组里记录的一致不一致就跳过。这样可以避免重复处理。3.3 初始化与边界条件的处理初始化部分看起来简单但有几个坑dist[S] 0cost[S] 0起点到自己距离和费用都是 0。其他所有点的dist初始化为无穷大cost也初始化为无穷大。如果起点和终点是同一个城市直接输出 0 0不需要跑算法。还有一个边界情况如果起点到终点根本不可达题目通常会保证有解但保险起见可以加一个判断。如果dist[D]仍然是无穷大说明不可达按题目要求输出通常是输出一个特定值或者不输出。另外关于无穷大的取值我一般用0x3f3f3f3f这个值大约是 10 亿两个相加不会溢出 int而且足够大能表示不可达。如果用INT_MAX相加的时候会溢出变成负数导致判断出错。这是一个非常经典的坑新手很容易踩。3.4 完整代码实现与逐行注释下面给出邻接矩阵版本的完整实现用的是 C因为 PTA 上大部分题目都支持 C而且写起来比较顺手。#include iostream #include cstring #include algorithm using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; int n, m, s, d; int len[MAXN][MAXN]; // 公路长度 int fee[MAXN][MAXN]; // 过路费 int dist[MAXN]; // 最短距离 int cost[MAXN]; // 最小费用 bool visited[MAXN]; // 是否已确定最短路 void dijkstra() { // 初始化 memset(dist, INF, sizeof(dist)); memset(cost, INF, sizeof(cost)); memset(visited, false, sizeof(visited)); dist[s] 0; cost[s] 0; for (int i 0; i n; i) { // 找当前未访问点中 dist 最小的 int u -1, minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } if (u -1) break; // 剩下的都不可达 visited[u] true; // 松弛邻居 for (int v 0; v n; v) { if (visited[v] || len[u][v] INF) continue; int newDist dist[u] len[u][v]; int newCost cost[u] fee[u][v]; if (newDist dist[v]) { // 情况一距离更短直接更新 dist[v] newDist; cost[v] newCost; } else if (newDist dist[v] newCost cost[v]) { // 情况二距离相同但费用更小 cost[v] newCost; } } } } int main() { cin n m s d; memset(len, INF, sizeof(len)); memset(fee, INF, sizeof(fee)); for (int i 0; i m; i) { int a, b, l, f; cin a b l f; // 处理重边保留长度更短或费用更小的 if (l len[a][b] || (l len[a][b] f fee[a][b])) { len[a][b] len[b][a] l; fee[a][b] fee[b][a] f; } } dijkstra(); cout dist[d] cost[d] endl; return 0; }这段代码里dijkstra函数的核心就是那个双重判断的松弛逻辑。注意我在找最小 dist 的时候用的是线性扫描因为邻接矩阵版本 N 通常不大O(N²) 完全够用。如果 N 很大就要换成优先队列。还有一个细节在输入阶段处理重边的时候我用了一个条件判断只有当新边的长度更短或者长度相同但费用更小的时候才更新。这样可以保证邻接矩阵里存的是最优的那条边。4. DFS 解法暴力枚举的可行性与剪枝思路4.1 什么时候该用 DFS 而不是 DijkstraDijkstra 是这道题的标准解法时间复杂度低、稳定性好。但 DFS 也不是完全不能用尤其是在数据规模很小的时候DFS 反而写起来更直观因为它的思路就是把所有路径都试一遍取最优的那条。DFS 的适用场景很明确N 比较小比如 N ≤ 20且图比较稀疏。因为 DFS 的时间复杂度是指数级的最坏情况下要枚举所有可能的路径N 稍微大一点就会超时。PTA 上这道题如果 N 到了几百DFS 是绝对过不了的。但是理解 DFS 的解法仍然有价值。一方面它能帮你验证 Dijkstra 的结果是否正确另一方面DFS 的剪枝思路在很多其他题目里都能用到。4.2 DFS 的核心框架与剪枝策略DFS 的基本框架是从起点出发递归地访问所有未访问的邻居到达终点时更新最优解然后回溯。void dfs(int u, int curLen, int curCost) { if (u d) { // 到达终点更新最优解 if (curLen bestLen || (curLen bestLen curCost bestCost)) { bestLen curLen; bestCost curCost; } return; } for (int v 0; v n; v) { if (!visited[v] len[u][v] ! INF) { // 剪枝如果当前长度已经超过最优长度直接跳过 if (curLen len[u][v] bestLen) continue; visited[v] true; dfs(v, curLen len[u][v], curCost fee[u][v]); visited[v] false; } } }这里有两个关键的剪枝长度剪枝如果当前路径长度已经超过了已知的最优长度就没必要继续往下走了因为长度只会增加不会减少。费用剪枝如果当前长度已经等于最优长度但费用已经超过了最优费用也可以剪掉。这两个剪枝能大幅减少搜索空间在数据规模不大的时候DFS 跑起来还是很快的。4.3 DFS 与 Dijkstra 的结果对比验证我一般会先用 Dijkstra 写一遍提交通过之后再用 DFS 写一遍用小数据对拍。对拍的方法很简单随机生成若干组小规模数据分别用两个程序跑比较输出是否一致。如果一致说明两个解法都是对的如果不一致说明至少有一个写错了。这种对拍的方法在刷题的时候非常有用尤其是当你对某个算法的正确性不太确定的时候。DFS 虽然慢但它的逻辑简单、不容易写错很适合作为参考答案来验证复杂算法的正确性。不过要注意DFS 在有多条等长路径的时候必须遍历完所有路径才能确定最小费用不能中途提前返回。这一点和 Dijkstra 不同Dijkstra 的贪心性质保证了它能在第一次到达终点时就确定最优解但 DFS 没有这个性质。5. 实际编码中踩过的坑与调试经验5.1 重边处理不当导致的答案错误这是我第一次做这道题时踩的坑。题目没有明确说两个城市之间会不会有多条公路我默认只有一条结果输入里出现了重边我的邻接矩阵被后输入的边覆盖了导致存的是费用更高或者长度更长的那条边答案自然就错了。后来我加了一个判断只有当新边的长度更短或者长度相同但费用更小的时候才更新邻接矩阵。这样就能保证存的是最优的那条边。这个坑其实很隐蔽因为如果测试数据里没有重边你的代码是能过的。但一旦有重边就会莫名其妙地错。所以我的建议是不管题目有没有说都默认可能有重边在输入阶段就处理好。5.2 费用更新后忘记重新入队的后果在用优先队列版本的 Dijkstra 时我遇到过一个很诡异的问题距离是对的但费用偶尔会偏大。排查了很久才发现是在情况二距离相同但费用更小的时候我只更新了cost[v]但没有把 v 重新加入优先队列。这样一来v 的费用虽然更新了但从 v 出发到其他点的路径费用没有跟着更新导致最终终点的费用不是最小的。修复方法很简单在费用更新的时候把 v 重新入队。然后在取出的时候加一个判断如果当前取出的距离和费用和数组里记录的不一致就跳过。这个坑的教训是Dijkstra 里任何一个数组的更新都可能影响到后续的松弛不能只更新不传播。5.3 无穷大取值与溢出问题前面提到过无穷大我一般用0x3f3f3f3f。这个值大约是 10 亿两个相加是 20 亿不会超过 int 的上限约 21 亿。如果用INT_MAX相加就会溢出变成负数导致newDist dist[v]这个判断出错。这个坑在写 Dijkstra 的时候特别常见因为松弛操作里经常要做加法。我的习惯是只要涉及加法无穷大就用0x3f3f3f3f并且用memset初始化的时候0x3f正好能让每个字节都是0x3f整个 int 就是0x3f3f3f3f。这是一个很实用的小技巧。5.4 起点等于终点的特殊情况如果起点和终点是同一个城市按照题意最短路径长度是 0费用也是 0。但有些人的代码在这种情况下会输出错误的结果因为 Dijkstra 的循环可能不会正确处理这种情况。我的处理方式是在跑 Dijkstra 之前先判断一下如果s d直接输出0 0然后返回。这样最省事也最不容易出错。5.5 输出格式的细节PTA 的题目对输出格式要求很严格多一个空格或者少一个换行都可能被判错。这道题通常是输出两个整数中间用一个空格隔开末尾换行。我一般用cout dist[d] cost[d] endl;这样最稳妥。有些题目会要求如果不可达输出特定内容这时候就要加判断。但 7-112 这道题通常保证有解所以不用太担心。6. 从这道题延伸出去双条件最短路的通用套路6.1 第二关键字可以是任何可比较的量这道题的第二关键字是费用要求最小。但实际上第二关键字可以是任何可比较的量比如时间、风险值、换乘次数等等。只要满足第一关键字优先第二关键字次之的优先级关系都可以用同样的套路处理。松弛逻辑的通用形式是if (newFirst first[v]) { 更新 first[v] 和 second[v]; } else if (newFirst first[v] newSecond second[v]) { 更新 second[v]; }这个模板可以套用到绝大多数双条件最短路问题上。6.2 如果第二关键字要求最大怎么办如果题目要求的是在最短路径中选费用最大的或者选时间最长的只需要把第二个判断里的小于号改成大于号就行了。逻辑完全一样只是比较方向变了。不过要注意如果第二关键字要求最大初始化的时候second[]要初始化为负无穷或者 0取决于具体问题而不是正无穷。6.3 三个及以上关键字怎么办如果题目有三个甚至更多关键字比如距离最短、费用最小、时间最少那处理起来就复杂一些。一种做法是定义一个结构体重载比较运算符然后按照优先级依次比较。另一种做法是给每个关键字分配一个权重把它们合成一个值但这种方法只适用于关键字之间可以线性组合的情况通用性不如结构体比较。对于三个关键字的情况松弛逻辑会变成if (newFirst first[v]) { 全部更新; } else if (newFirst first[v]) { if (newSecond second[v]) { 更新 second 和 third; } else if (newSecond second[v] newThird third[v]) { 更新 third; } }逻辑虽然变复杂了但本质上还是按优先级依次比较。6.4 这道题对理解 Dijkstra 本质的帮助做完这道题之后我对 Dijkstra 的理解深了不少。以前只是把它当成一个模板来背知道怎么用但不知道为什么这么用。这道题逼着我去思考为什么 Dijkstra 能在第一次取出某个点的时候就确定它的最短路为什么在等长路径中选最小费用不会破坏贪心性质想清楚这些问题之后再遇到类似的变种题就不会慌了。因为你知道算法的核心在哪里知道哪些地方可以改、哪些地方不能改。7. 一些实用的调试技巧和刷题建议7.1 用对拍验证正确性前面提到过对拍这里再展开说一下。对拍的基本流程是写一个暴力程序比如 DFS保证逻辑简单、不容易错。写一个高效程序比如 Dijkstra这是你要提交的版本。写一个数据生成器随机生成小规模测试数据。循环运行两个程序比较输出。如果发现不一致就保存这组数据手动分析。对拍能帮你发现很多边界情况下的错误比如重边、自环、不可达等等。这些情况在手动构造的测试数据里很容易被忽略但随机生成的数据往往能覆盖到。7.2 手动构造边界测试用例除了对拍手动构造一些边界用例也很有必要。比如起点等于终点只有一条边有重边有自环虽然这道题通常没有所有边的费用都是 0所有边的长度都是 0这些用例能帮你检查代码的鲁棒性。我一般会在提交之前把这些用例都跑一遍确认输出符合预期。7.3 关于 PTA 平台的提交注意事项PTA 的判题比较严格有几个地方要注意输出格式必须完全匹配包括空格和换行。如果题目有多组输入要循环处理直到文件结束。数组大小要开够不要刚好卡在边界上多开一点更安全。如果用 C注意cin和cout的效率数据量大的时候可以加ios::sync_with_stdio(false);。这道题的数据量通常不大用cin和cout完全没问题。但如果遇到大数据量的题目就要考虑换成scanf和printf或者关掉同步。7.4 刷题时的心态调整最后说点心态上的东西。这道题我前前后后改了三四次才过中间一度怀疑自己是不是不适合写代码。但后来发现每次出错其实都是在补一个知识盲区第一次是重边没处理第二次是费用更新没传播第三次是无穷大溢出。每改一次对算法的理解就深一层。所以刷题的时候不要怕错也不要怕改。错得越多学到的东西越多。关键是每次错之后都要搞清楚为什么错而不是随便改改碰运气。 
长河君 · 2026/10/13 9:05:18 · 阅读 1.2k PTA旅游规划双条件最短路：Dijkstra与DFS解法详解
1. 从旅游规划这道题看最短路径问题的双重解法PTA 7-112 旅游规划这道题在数据结构与算法的练习里算是很经典的一道综合题。它表面上是一个旅游路线规划的场景实际上考察的是带权无向图上的最短路径求解而且不是单纯求一条最短路还要在多条最短路中选出花费最少的那一条。这个双重条件的设计是这道题最核心的考点也是很多人第一次做的时候容易翻车的地方。我最初看到这道题的时候第一反应是不就是 Dijkstra 吗结果写完提交发现只过了一半的测试点。后来仔细读题才发现题目要求的是在保证路径总长度最短的前提下如果存在多条长度相同的最短路径要选择过路费总和最小的那条。这就意味着标准的 Dijkstra 模板不能直接套用需要在松弛操作里额外维护一个费用维度。这道题适合谁看如果你正在刷 PTA 的图论专题或者正在准备数据结构考试、算法面试又或者你只是想把 Dijkstra 和 DFS 这两个基础算法真正吃透那这道题是一个非常好的练手素材。它不像纯粹的模板题那样机械也不像复杂的网络流那样劝退刚好卡在一个需要动脑子但又不至于无从下手的难度区间。接下来我会从题目建模、Dijkstra 的双关键字处理、DFS 的暴力验证思路、以及实际编码中踩过的坑这几个角度把这道题彻底拆开讲清楚。文章里给出的代码和思路都是可以直接复现的你照着敲一遍基本就能把这类双条件最短路问题一次性拿下。2. 题目建模把旅游场景翻译成图论语言2.1 城市是点公路是边两个权重分别是什么拿到任何一道图论题第一步永远是把自然语言描述翻译成图的结构。这道题里城市就是图中的顶点vertex两个城市之间的公路就是图中的边edge。题目给的是无向图因为公路是双向通行的。关键在于每条边上有两个权重公路长度这是第一优先级我们要让总长度最小。过路费这是第二优先级在总长度相同的情况下让总费用最小。用邻接矩阵或者邻接表存储的时候每条边需要同时记录这两个值。我一般习惯用结构体或者两个独立的二维数组来存具体看个人习惯。如果用邻接矩阵可以开两个数组dist[i][j]和cost[i][j]分别表示城市 i 到城市 j 的公路长度和过路费。这里有个细节要注意题目中两个城市之间可能有多条公路虽然经典版本通常假设只有一条但保险起见要处理。如果有多条应该保留长度最短的那条如果长度也相同保留费用最小的那条。这个处理逻辑在输入阶段就要做好否则后面 Dijkstra 会出错。2.2 起点、终点和输出要求题目一般会给定起点城市 S 和终点城市 D要求输出最短路径的长度以及该路径上的总过路费。有些版本还会要求输出路径本身但 7-112 这道题通常只要求输出两个数值。输出格式看起来简单但恰恰是这里容易出问题。因为当存在多条最短路径时你输出的费用必须是所有最短路径中最小的那个费用而不是你随便找到的那条路径的费用。这就要求算法在求解过程中必须能够正确地在等长路径中挑最小费用。我见过不少人的代码Dijkstra 只维护了距离数组费用是在最后回溯路径的时候才累加的。这种做法在单条最短路的情况下没问题但一旦有多条等长路径回溯出来的那条未必是费用最小的那条结果就错了。正确的做法是在松弛阶段就把费用作为第二关键字一起更新。2.3 数据规模的判断与存储结构选择在动手写代码之前先看一眼数据范围。PTA 上这类题目的城市数量 N 通常在几百到一千左右边数 M 在几千到几万不等。这个规模下几种存储方式都是可行的存储方式时间复杂度空间复杂度适用场景邻接矩阵O(N²)O(N²)N ≤ 1000 时够用邻接表 优先队列O(M log N)O(N M)稀疏图首选邻接表 普通队列O(N²)O(N M)稠密图也可如果 N 在 500 以内邻接矩阵写起来最省事Dijkstra 直接双重循环找最小值就行代码短、不易出错。如果 N 到了几千甚至上万那就必须上邻接表加优先队列否则会超时。我的建议是先用邻接矩阵把逻辑跑通确认答案正确之后如果超时再改成优先队列版本。这样调试成本最低因为邻接矩阵版本的 Dijkstra 逻辑最直观出错了也容易定位。3. Dijkstra 的双关键字松弛这道题真正的难点3.1 标准 Dijkstra 为什么不够用标准的 Dijkstra 算法维护一个dist[]数组表示从起点到每个点的最短距离。每次从优先队列里取出当前距离最小的点然后遍历它的邻居如果dist[u] w(u,v) dist[v]就更新dist[v]。这个逻辑在处理单一权重的时候是完全正确的因为 Dijkstra 的贪心性质保证了一旦某个点被取出它的最短距离就已经确定不会再被更新。但是这道题有两个权重而且两个权重有优先级之分。距离是第一优先级费用是第二优先级。当dist[u] w(u,v) dist[v]的时候标准 Dijkstra 不会做任何操作但这时候我们其实需要检查通过 u 到达 v 的这条路径费用是不是比当前记录的到 v 的费用更小如果是就要更新费用。这就是这道题的核心改动点松弛条件从单一的小于号变成了小于或者等于但费用更小。3.2 松弛操作的完整逻辑拆解我把松弛部分的逻辑单独拎出来讲因为这里是整道题最容易写错的地方。假设当前从优先队列取出的是节点 u它的最短距离是dist[u]最小费用是cost[u]。现在遍历 u 的邻居 v边 (u,v) 的长度是len费用是fee。那么从 u 到 v 的新路径长度是dist[u] len新费用是cost[u] fee。接下来分三种情况情况一新路径长度小于当前dist[v]这说明找到了一条更短的路不管费用多少都要更新。执行dist[v] dist[u] len; cost[v] cost[u] fee; 把 v 加入优先队列;情况二新路径长度等于当前dist[v]但新费用小于当前cost[v]这说明找到了一条等长但更便宜的路需要更新费用。执行cost[v] cost[u] fee; 把 v 加入优先队列或者只更新费用视实现而定;情况三新路径长度大于当前dist[v]直接忽略因为距离已经不是最优了费用再小也没意义。这里有个容易忽略的点在情况二里距离没有变只是费用变小了。这时候要不要把 v 重新加入优先队列答案是要。因为 v 的费用变了从 v 出发到其他点的路径费用也可能因此变小需要重新松弛 v 的邻居。如果不重新入队就可能漏掉后续的费用更新。不过这里也有一个优化技巧如果用的是优先队列可以只在费用更新时把 v 重新入队然后在取出的时候判断一下当前取出的距离和费用是否和数组里记录的一致不一致就跳过。这样可以避免重复处理。3.3 初始化与边界条件的处理初始化部分看起来简单但有几个坑dist[S] 0cost[S] 0起点到自己距离和费用都是 0。其他所有点的dist初始化为无穷大cost也初始化为无穷大。如果起点和终点是同一个城市直接输出 0 0不需要跑算法。还有一个边界情况如果起点到终点根本不可达题目通常会保证有解但保险起见可以加一个判断。如果dist[D]仍然是无穷大说明不可达按题目要求输出通常是输出一个特定值或者不输出。另外关于无穷大的取值我一般用0x3f3f3f3f这个值大约是 10 亿两个相加不会溢出 int而且足够大能表示不可达。如果用INT_MAX相加的时候会溢出变成负数导致判断出错。这是一个非常经典的坑新手很容易踩。3.4 完整代码实现与逐行注释下面给出邻接矩阵版本的完整实现用的是 C因为 PTA 上大部分题目都支持 C而且写起来比较顺手。#include iostream #include cstring #include algorithm using namespace std; const int MAXN 505; const int INF 0x3f3f3f3f; int n, m, s, d; int len[MAXN][MAXN]; // 公路长度 int fee[MAXN][MAXN]; // 过路费 int dist[MAXN]; // 最短距离 int cost[MAXN]; // 最小费用 bool visited[MAXN]; // 是否已确定最短路 void dijkstra() { // 初始化 memset(dist, INF, sizeof(dist)); memset(cost, INF, sizeof(cost)); memset(visited, false, sizeof(visited)); dist[s] 0; cost[s] 0; for (int i 0; i n; i) { // 找当前未访问点中 dist 最小的 int u -1, minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } if (u -1) break; // 剩下的都不可达 visited[u] true; // 松弛邻居 for (int v 0; v n; v) { if (visited[v] || len[u][v] INF) continue; int newDist dist[u] len[u][v]; int newCost cost[u] fee[u][v]; if (newDist dist[v]) { // 情况一距离更短直接更新 dist[v] newDist; cost[v] newCost; } else if (newDist dist[v] newCost cost[v]) { // 情况二距离相同但费用更小 cost[v] newCost; } } } } int main() { cin n m s d; memset(len, INF, sizeof(len)); memset(fee, INF, sizeof(fee)); for (int i 0; i m; i) { int a, b, l, f; cin a b l f; // 处理重边保留长度更短或费用更小的 if (l len[a][b] || (l len[a][b] f fee[a][b])) { len[a][b] len[b][a] l; fee[a][b] fee[b][a] f; } } dijkstra(); cout dist[d] cost[d] endl; return 0; }这段代码里dijkstra函数的核心就是那个双重判断的松弛逻辑。注意我在找最小 dist 的时候用的是线性扫描因为邻接矩阵版本 N 通常不大O(N²) 完全够用。如果 N 很大就要换成优先队列。还有一个细节在输入阶段处理重边的时候我用了一个条件判断只有当新边的长度更短或者长度相同但费用更小的时候才更新。这样可以保证邻接矩阵里存的是最优的那条边。4. DFS 解法暴力枚举的可行性与剪枝思路4.1 什么时候该用 DFS 而不是 DijkstraDijkstra 是这道题的标准解法时间复杂度低、稳定性好。但 DFS 也不是完全不能用尤其是在数据规模很小的时候DFS 反而写起来更直观因为它的思路就是把所有路径都试一遍取最优的那条。DFS 的适用场景很明确N 比较小比如 N ≤ 20且图比较稀疏。因为 DFS 的时间复杂度是指数级的最坏情况下要枚举所有可能的路径N 稍微大一点就会超时。PTA 上这道题如果 N 到了几百DFS 是绝对过不了的。但是理解 DFS 的解法仍然有价值。一方面它能帮你验证 Dijkstra 的结果是否正确另一方面DFS 的剪枝思路在很多其他题目里都能用到。4.2 DFS 的核心框架与剪枝策略DFS 的基本框架是从起点出发递归地访问所有未访问的邻居到达终点时更新最优解然后回溯。void dfs(int u, int curLen, int curCost) { if (u d) { // 到达终点更新最优解 if (curLen bestLen || (curLen bestLen curCost bestCost)) { bestLen curLen; bestCost curCost; } return; } for (int v 0; v n; v) { if (!visited[v] len[u][v] ! INF) { // 剪枝如果当前长度已经超过最优长度直接跳过 if (curLen len[u][v] bestLen) continue; visited[v] true; dfs(v, curLen len[u][v], curCost fee[u][v]); visited[v] false; } } }这里有两个关键的剪枝长度剪枝如果当前路径长度已经超过了已知的最优长度就没必要继续往下走了因为长度只会增加不会减少。费用剪枝如果当前长度已经等于最优长度但费用已经超过了最优费用也可以剪掉。这两个剪枝能大幅减少搜索空间在数据规模不大的时候DFS 跑起来还是很快的。4.3 DFS 与 Dijkstra 的结果对比验证我一般会先用 Dijkstra 写一遍提交通过之后再用 DFS 写一遍用小数据对拍。对拍的方法很简单随机生成若干组小规模数据分别用两个程序跑比较输出是否一致。如果一致说明两个解法都是对的如果不一致说明至少有一个写错了。这种对拍的方法在刷题的时候非常有用尤其是当你对某个算法的正确性不太确定的时候。DFS 虽然慢但它的逻辑简单、不容易写错很适合作为参考答案来验证复杂算法的正确性。不过要注意DFS 在有多条等长路径的时候必须遍历完所有路径才能确定最小费用不能中途提前返回。这一点和 Dijkstra 不同Dijkstra 的贪心性质保证了它能在第一次到达终点时就确定最优解但 DFS 没有这个性质。5. 实际编码中踩过的坑与调试经验5.1 重边处理不当导致的答案错误这是我第一次做这道题时踩的坑。题目没有明确说两个城市之间会不会有多条公路我默认只有一条结果输入里出现了重边我的邻接矩阵被后输入的边覆盖了导致存的是费用更高或者长度更长的那条边答案自然就错了。后来我加了一个判断只有当新边的长度更短或者长度相同但费用更小的时候才更新邻接矩阵。这样就能保证存的是最优的那条边。这个坑其实很隐蔽因为如果测试数据里没有重边你的代码是能过的。但一旦有重边就会莫名其妙地错。所以我的建议是不管题目有没有说都默认可能有重边在输入阶段就处理好。5.2 费用更新后忘记重新入队的后果在用优先队列版本的 Dijkstra 时我遇到过一个很诡异的问题距离是对的但费用偶尔会偏大。排查了很久才发现是在情况二距离相同但费用更小的时候我只更新了cost[v]但没有把 v 重新加入优先队列。这样一来v 的费用虽然更新了但从 v 出发到其他点的路径费用没有跟着更新导致最终终点的费用不是最小的。修复方法很简单在费用更新的时候把 v 重新入队。然后在取出的时候加一个判断如果当前取出的距离和费用和数组里记录的不一致就跳过。这个坑的教训是Dijkstra 里任何一个数组的更新都可能影响到后续的松弛不能只更新不传播。5.3 无穷大取值与溢出问题前面提到过无穷大我一般用0x3f3f3f3f。这个值大约是 10 亿两个相加是 20 亿不会超过 int 的上限约 21 亿。如果用INT_MAX相加就会溢出变成负数导致newDist dist[v]这个判断出错。这个坑在写 Dijkstra 的时候特别常见因为松弛操作里经常要做加法。我的习惯是只要涉及加法无穷大就用0x3f3f3f3f并且用memset初始化的时候0x3f正好能让每个字节都是0x3f整个 int 就是0x3f3f3f3f。这是一个很实用的小技巧。5.4 起点等于终点的特殊情况如果起点和终点是同一个城市按照题意最短路径长度是 0费用也是 0。但有些人的代码在这种情况下会输出错误的结果因为 Dijkstra 的循环可能不会正确处理这种情况。我的处理方式是在跑 Dijkstra 之前先判断一下如果s d直接输出0 0然后返回。这样最省事也最不容易出错。5.5 输出格式的细节PTA 的题目对输出格式要求很严格多一个空格或者少一个换行都可能被判错。这道题通常是输出两个整数中间用一个空格隔开末尾换行。我一般用cout dist[d] cost[d] endl;这样最稳妥。有些题目会要求如果不可达输出特定内容这时候就要加判断。但 7-112 这道题通常保证有解所以不用太担心。6. 从这道题延伸出去双条件最短路的通用套路6.1 第二关键字可以是任何可比较的量这道题的第二关键字是费用要求最小。但实际上第二关键字可以是任何可比较的量比如时间、风险值、换乘次数等等。只要满足第一关键字优先第二关键字次之的优先级关系都可以用同样的套路处理。松弛逻辑的通用形式是if (newFirst first[v]) { 更新 first[v] 和 second[v]; } else if (newFirst first[v] newSecond second[v]) { 更新 second[v]; }这个模板可以套用到绝大多数双条件最短路问题上。6.2 如果第二关键字要求最大怎么办如果题目要求的是在最短路径中选费用最大的或者选时间最长的只需要把第二个判断里的小于号改成大于号就行了。逻辑完全一样只是比较方向变了。不过要注意如果第二关键字要求最大初始化的时候second[]要初始化为负无穷或者 0取决于具体问题而不是正无穷。6.3 三个及以上关键字怎么办如果题目有三个甚至更多关键字比如距离最短、费用最小、时间最少那处理起来就复杂一些。一种做法是定义一个结构体重载比较运算符然后按照优先级依次比较。另一种做法是给每个关键字分配一个权重把它们合成一个值但这种方法只适用于关键字之间可以线性组合的情况通用性不如结构体比较。对于三个关键字的情况松弛逻辑会变成if (newFirst first[v]) { 全部更新; } else if (newFirst first[v]) { if (newSecond second[v]) { 更新 second 和 third; } else if (newSecond second[v] newThird third[v]) { 更新 third; } }逻辑虽然变复杂了但本质上还是按优先级依次比较。6.4 这道题对理解 Dijkstra 本质的帮助做完这道题之后我对 Dijkstra 的理解深了不少。以前只是把它当成一个模板来背知道怎么用但不知道为什么这么用。这道题逼着我去思考为什么 Dijkstra 能在第一次取出某个点的时候就确定它的最短路为什么在等长路径中选最小费用不会破坏贪心性质想清楚这些问题之后再遇到类似的变种题就不会慌了。因为你知道算法的核心在哪里知道哪些地方可以改、哪些地方不能改。7. 一些实用的调试技巧和刷题建议7.1 用对拍验证正确性前面提到过对拍这里再展开说一下。对拍的基本流程是写一个暴力程序比如 DFS保证逻辑简单、不容易错。写一个高效程序比如 Dijkstra这是你要提交的版本。写一个数据生成器随机生成小规模测试数据。循环运行两个程序比较输出。如果发现不一致就保存这组数据手动分析。对拍能帮你发现很多边界情况下的错误比如重边、自环、不可达等等。这些情况在手动构造的测试数据里很容易被忽略但随机生成的数据往往能覆盖到。7.2 手动构造边界测试用例除了对拍手动构造一些边界用例也很有必要。比如起点等于终点只有一条边有重边有自环虽然这道题通常没有所有边的费用都是 0所有边的长度都是 0这些用例能帮你检查代码的鲁棒性。我一般会在提交之前把这些用例都跑一遍确认输出符合预期。7.3 关于 PTA 平台的提交注意事项PTA 的判题比较严格有几个地方要注意输出格式必须完全匹配包括空格和换行。如果题目有多组输入要循环处理直到文件结束。数组大小要开够不要刚好卡在边界上多开一点更安全。如果用 C注意cin和cout的效率数据量大的时候可以加ios::sync_with_stdio(false);。这道题的数据量通常不大用cin和cout完全没问题。但如果遇到大数据量的题目就要考虑换成scanf和printf或者关掉同步。7.4 刷题时的心态调整最后说点心态上的东西。这道题我前前后后改了三四次才过中间一度怀疑自己是不是不适合写代码。但后来发现每次出错其实都是在补一个知识盲区第一次是重边没处理第二次是费用更新没传播第三次是无穷大溢出。每改一次对算法的理解就深一层。所以刷题的时候不要怕错也不要怕改。错得越多学到的东西越多。关键是每次错之后都要搞清楚为什么错而不是随便改改碰运气。