这个标题一出来熟悉图论题的朋友应该已经嗅到味道了——它跟普通最短路最大的区别就是多了“反转”两个字。我第一次做这类题时第一反应是“直接跑Dijkstra不就行了”结果建图建到一半发现完全不是那么回事如果允许逆着边的方向走代价是什么反转一次是多少钱这题到底让你求的是“反转次数”还是“路径上所有边的总成本”这些不搞清楚代码写出来必挂。这篇文章我把这类题的完整思考链路拆开讲从题意翻译、暴力思路为什么不行到0-1 BFS、泛化Dijkstra再到“最小拐弯路径”这类同构问题最后是WA陷阱复盘争取让没做过这类题的人也能一次性吃透。1. “边反转”到底在考什么先把题意翻译成图模型1.1 题目里的人话版本题目给了你一张有向图每条边都有一个原始方向和一个权值。正常情况下从u走到v只能沿着u-v的方向走但如果这条路很重要你也可以选择“反转”这条边让它变成v-u代价是要额外付一笔反转成本。题目要求从起点s到终点t的最小总成本总成本 所有走过的边的基础权值之和 被反转的边的反转成本之和。简化理解每条有向边相当于一条“单行道”。顺向走不花钱逆向走要先掏钱改方向。问从入口到出口最少花多少钱。这个模型在现实中太常见了。最直观的是单行道系统导航让你绕路是因为逆向要申请、要罚款本质上就是个“反转代价”。再比如网络链路端口默认方向是A到B现在流量想从B到A要么走别的路径要么调整配置调整配置就是成本。所以这道题考的不是“你会不会最短路”而是“你能不能把额外条件翻译进图里”。1.2 边的两种走法要分开记账很多新手卡在第一步一条有向边到底该怎么塞进邻接表实际上对于有向边u-v你的选择有两个沿原始方向u-v走花费是边的基础权值w不需要反转逆着原始方向走即从v到u需要先反转这条边花费是w 该边的反转代价r。所以建图时一条边至少要拆成两条弧来存原方向弧u-v权值为w反向弧v-u权值为wr。这两条弧不是对称的——如果w和r不相等或者不同边的r不一样它们就是两条完全独立的弧。这个“拆弧”动作就是整个题的核心。我当时在这上面栽过跟头把反向弧的权值直接写成w想着“反正反转一次就完了”结果样例过、提交WA。原因很简单反转代价是额外开销不是边权本身的一部分两者相加才是逆向通行的真实成本。注意这里w和r是同一个规模概念吗题目如果只说了“基础边权”和“反转成本”没有单独给每条边的r那r通常就是一个全局常数比如1。反之如果每条边有自己的反转成本就按每条边分别存。做之前先确认好别在题意上猜。1.3 规模决定算法选型这类“每日一题”级别的题n和m一般都在10^5量级。n10^5、m10^5是标配所以Floyd这类O(n^3)算法直接出局朴素Dijkstra O(n^2)也危险堆优化Dijkstra O((nm)log n)稳过边权只有0和1时0-1 BFS能做到O(nm)是理论最优。我后面会先讲0-1 BFS版本因为它最好地展示了“反转”这个动作如何被编码成0/1权值再讲任意反转成本的Dijkstra版本这样从特殊到一般理解更扎实。2. 暴力思路为什么挂掉两种典型错误2.1 直接DFS枚举所有路径组合拿到题最容易想到的办法是DFS从起点出发每条边可以顺着走也可以选择反转后倒着走尝试所有可能组合。但稍微算一下就知道这条路走不通每条边有两种走法路径长度最坏可以到n路径条数是指数级增长的n100就爆炸更别说10^5。还有更尴尬的问题如果允许“先反转A边走过去再反转A边走回来”路径中可能会反复经过同一条边DFS要处理访问标记但你根本没法判断“经过一次”和“经过三次”哪个更优因为可能某些反转组合会导致更小的总成本不存在的——边权非负时绕圈只会增加总成本但DFS很难证明这件事写起来还一堆边界条件。2.2 朴素“拆边建图”的状态爆炸既然每条边有两个方向那把每条边拆成两条有向弧然后在拆出来的图上跑最短路行不行单看建图这一步是行的我上面建图方案本质上也是拆边。但很多人折在“拆完边之后没有控制状态”。举个例子一条边拆成两条弧之后同一个节点可能通过“原方向弧”和“反向弧”分别到达在这两种状态之间切换时是否还需要额外代价如果你不把这个代价建模进去最短路算出来的结果就是错的。更典型的问题是有的人会把“反转”当成一个全局开关——反转一次整张图的方向都变了。这就完全错了。题目说的是“边反转”是每条边单独反转不是全球反转。一旦按全局反转建模图就变成了一张动态图状态瞬间爆炸最短路直接失效。我见过有人把“反转代价”当成“是否使用某条边的代价”然后写了个状压DP。点少的时候也许能过但m一大就彻底歇菜。这类题考的就是最短路不是搜索剪枝。3. 0-1 BFS反转成本为1时的最优做法3.1 把“反转”编码成边权0和1如果题目里所有边的反转成本都是1或者你只关心“最少反转几次能到终点”问题就可以极大地简化沿原始方向u-v走反转次数不增加边权记为0从v反向走到u需要反转一次边权记为1。这样问题就变成了一张边权只有0和1的图求s到t的最短路。这个场景用0-1 BFS是最舒服的因为它的复杂度只有O(nm)比堆优化Dijkstra还少一个log。为什么能这样编码因为“反转次数”是独立的、可计数的。每一次逆着边走就是一次反转累计次数就是这条路径的反转总成本。边的基础权值在这个版本里先不看或者假设所有边的基础权值相同反正不影响“最少反转次数”这个核心量。3.2 双端队列为什么能替代优先队列0-1 BFS原理不复杂但很多人只记住了“0权边塞队头1权边塞队尾”没搞懂为什么对一变形就懵。普通BFS能找到无权图最短路靠的是队列中节点的距离单调不减先弹出的距离小后弹出的距离大。边权变成0或1之后如果向队尾插入距离1的节点队列仍然保持单调如果向队头插入距离0的节点这个距离和当前节点的距离一样插到队头也不会破坏单调性。所以双端队列在这种情况下完美替代了优先队列。核心结论每个节点第一次弹出队列时它的距离一定是最小的。这个结论和Dijkstra的“出队即最优”一脉相承只是0-1 BFS用deque实现了优先队列的效果省掉了log。提示0-1 BFS要求边权只能是0或1且都非负。如果出现负数deque直接失效必须上SPFA或带负权的最短路算法——但这类题一般不会出负权因为反转成本不可能为负。3.3 完整代码与逐行解释#include bits/stdc.h using namespace std; const int maxn 100005; const int INF 0x3f3f3f3f; struct Edge { int to, w; // w 0 表示沿原始方向走不需要反转 // w 1 表示逆着原始方向走需要反转1次 }; vectorEdge g[maxn]; int dist[maxn]; bool vis[maxn]; void bfs01(int s, int n) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; dequeint dq; dq.push_front(s); while (!dq.empty()) { int u dq.front(); dq.pop_front(); if (vis[u]) continue; vis[u] true; for (auto e : g[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; if (e.w 0) dq.push_front(e.to); else dq.push_back(e.to); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin n m s t; for (int i 0; i m; i) { int u, v; cin u v; // 原始方向 u - v不需要反转 g[u].push_back({v, 0}); // 反向 v - u需要反转1次 g[v].push_back({u, 1}); } bfs01(s, n); if (dist[t] INF) cout -1 \n; else cout dist[t] \n; return 0; }每行代码都很直白但有几个点要强调vis数组在出队时标记不是入队时。这个区别极其关键我后面专门用一章讲为什么。dist初始化为0x3f3f3f3f这个值约等于10^9在本题数据范围内是安全的“无穷大”。输入规模大的时候ios::sync_with_stdio(false)一定要写否则cin可能成为性能瓶颈。你可以把这份代码直接交上去跑一遍再把“最少反转次数”和题目要求的最小总成本对照一下。如果题目要求的是基础权值反转代价的总和那就得看下一章的泛化版本。4. 从0-1到任意权升级到堆优化Dijkstra4.1 建图权值的完整公式当每条边除了反转成本还有自己的基础边权w时“最少反转次数”已经不够了。比如有一条路基础边权是100但不需要反转另一条路基础边权是1但需要反转2次光看反转次数显然会选错路。正确的建图方式是原方向u-v边权为w反方向v-u边权为w r其中r是这条边的反转成本。每条有向边拆成两条弧两条弧的权值不同。这和0-1版本的思路一模一样只是把“0”和“1”换成了任意非负整数。如果题目里没有单独给出每条边的r只是给了一个全局反转成本那r就是个常数如果r为0那就直接退化成了普通有向图最短路。所以这个模型是通吃的。4.2 堆优化Dijkstra模板#include bits/stdc.h using namespace std; typedef long long ll; const int maxn 100005; const ll INF 1e18; struct Edge { int to; ll w; }; vectorEdge g[maxn]; ll dist[maxn]; void dijkstra(int s, int n) { for (int i 0; i n; i) dist[i] INF; dist[s] 0; priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期节点跳过 for (auto e : g[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin n m s t; for (int i 0; i m; i) { int u, v; ll w, r; cin u v w r; g[u].push_back({v, w}); // 原始方向 g[v].push_back({u, w r}); // 反转方向 } dijkstra(s, n); if (dist[t] INF) cout -1 \n; else cout dist[t] \n; return 0; }这里有个和0-1 BFS不同的地方Dijkstra的判断不是vis数组而是if (d ! dist[u]) continue;。这行代码的作用是跳过已经过期的堆节点。为什么可以这样因为一个节点可能被多条路径多次更新入堆只有当前dist[u]对应的那一次弹出才是有效的其他都是旧数据直接丢弃。4.3 两类算法的统一视角0-1 BFS其实是Dijkstra在边权∈{0,1}时的特例。为什么能省log因为边权种类少双端队列天然维护了单调性边权种类多了之后deque就不够用了必须用优先队列。写题的时候判断到底该用哪个条件算法复杂度边权只有0和1求最短/最少次数0-1 BFSO(nm)边权为非负整数求最小总成本堆优化DijkstraO((nm)log n)存在负权边SPFA或Bellman-FordO(nm)从0-1推广到任意权核心的建图思想完全没变把“选择”翻译成“边权”。原方向走不走、反转后走不走是两条路各自标好价格剩下的交给最短路模板。5. 题外同理“最小拐弯路径”1444到底在考什么5.1 拐弯代价和反转代价本质一样看标题觉得“边反转”和“最小拐弯”八竿子打不着其实它们是同一族问题。“最小拐弯路径”的经典场景是在一个网格图或者道路网中从起点到终点允许上下左右移动但每拐一次弯方向发生变化需要付出一次代价求最小拐弯次数。把“拐弯”和“反转”放在一起看边反转问题逆着边的方向走付出反转代价拐弯问题改变了当前移动方向付出拐弯代价。两者的共同点是存在一个额外的状态状态切换需要成本。边反转的额外状态是“边是否被反转”拐弯问题的额外状态是“当前前进方向”。你在建模时只要把这个状态加进去问题就变成了分层图最短路。5.2 分层图的通用建模模板以网格中的最小拐弯路径为例标准建模方式是这样的把每个网格拆成4个状态节点分别代表“从上方进入”“从下方进入”“从左方进入”“从右方进入”同一网格、不同进入方向之间连边权值为1表示“在这里拐了一个弯”沿当前方向继续前进到相邻网格连边权值为0表示“没拐弯”起点和终点是4个状态节点的超源/超汇互相之间连边权值为0。建完图后在这个分层图上跑0-1 BFS或Dijkstra答案就出来了。// 伪代码拐弯问题状态节点建模 // state (grid_id, dir) // dir: 0上, 1下, 2左, 3右 for each grid with quad states: for i in 0..3: for j in 0..3: if i j: continue; add_edge(grid_i, grid_j, 1); // 拐弯代价 // 沿当前方向走到相邻格子 next grid direction[i]; if next valid: add_edge(grid_i, next_i, 0); // 直行代价0这个模板可以背下来因为它能解决一大类“方向/状态切换有代价”的最短路题。从边反转到拐弯路径再到“换乘最短路”地铁换乘一次加多少钱本质上都是同一个东西。5.3 反转次数有限制时的状态扩展还有一种常见变体题目说最多允许反转k次求在这个限制下的最小总成本。这时候就需要把“已反转次数”也加入状态形成三维分层图状态(u, cnt)表示“当前在节点u已经反转了cnt次”原方向走到v状态变为(v, cnt)代价w反方向走到v状态变为(v, cnt1)代价wr如果cnt1 k这条转移就不可用。最终答案是所有(t, cnt)中0 cnt k的最小距离。这种“维度扩展”的思路在竞赛里叫“分层图最短路”。理解了边反转就理解了分层图的入门理解了拐弯问题就理解了状态切换的最短路。三条题串在一起才是完整的知识网络。6. 边界条件与WA陷阱排查这一章我想专门聊一聊交上去“样例全过、提交全WA”的经典原因。这些问题我基本都踩过列出来帮你省时间。6.1 访问标记的时序问题入队标记 vs 出队标记0-1 BFS里最隐蔽的坑就是vis标记的时机。先看错误写法// 错误示范入队时标记 while (!dq.empty()) { int u dq.front(); dq.pop_front(); for (auto e : g[u]) { if (!vis[e.to]) { vis[e.to] true; // 错在这里 dist[e.to] dist[u] e.w; if (e.w 0) dq.push_front(e.to); else dq.push_back(e.to); } } }这段代码在普通BFS里没问题但在0-1 BFS里会算错。原因在于一个节点可能先通过一条“权值较大的路径”被入队并标记可之后有一条“权值更小的路径”才到达它但因为已经被标记更优的更新被跳过了。举个例子0 - 1 权值为1 0 - 2 权值为0 2 - 1 权值为0真实的最短路是0 - 2 - 1总权值为0。但如果入队时标记从0扩展节点1的dist先被设为1标记vis[1]true放入队尾节点2的dist设为0放入队头从2扩展发现vis[1]已经是true跳过更新。最后dist[1]是1但正确答案是0。这就是入队标记的错误后果。正确做法是出队时判断while (!dq.empty()) { int u dq.front(); dq.pop_front(); if (vis[u]) continue; vis[u] true; ... }这样保证每个节点第一次出队时它的dist已经是全局最小值之后再也不会被更新。这个经验同样适用于0-1 BFS的变体和带优先队列的DijkstraDijkstra用d ! dist[u]跳过也是同一种思想。6.2 起点等于终点如果s t答案是0不需要跑任何算法。这个特判可以在读入后直接处理也可以让最短路算法自然给出0。但如果你初始化的dist没设置对或者建图时把起点终点搞混就很容易出问题。6.3 重边和自环图中可能存在多条边连接同一对节点也可能存在u-u的自环。重边不一定要去重最短路算法会自动选择权值小的那条。但要注意如果两条重边的方向相反建图时都得加进去一条是原方向、另一条的反向弧也要单独建。自环u-u的原方向边权值为0反向边权值为wr。0-1 BFS中自环可能会让节点被重复压入队列但因为有出队标记不会死循环最多是多几次无效扩展。Dijkstra同理优先队列会自然跳过无效项。6.4 INF的选择和long long如果总成本可能超过int范围一定要用long long。我之前用int交过n10^5、m10^5边权全随机总成本轻松上10^10int直接溢出变成负数然后最短路算法就“正常”地跑出了错误答案。选择INF时建议如果是int用0x3f3f3f3f它小于INT_MAX且加上任意值仍然在int范围内不溢出如果是long long用1e18或者4e18别用INT_MAX误导自己。判断是否存在可行路径时只需要看dist[t]是否还是INF。如果输出-1是题目要求就输出-1不要求的话也可以直接输出dist[t]因为不可达时它是INF但注意别把INF当答案输出。6.5 输入输出效率10^5级别的边数cin不关同步确实能TLE。我的习惯是写ios::sync_with_stdio(false); cin.tie(nullptr);如果题目输入规模特别大用scanf或快读也行。这些细节虽然不涉及算法核心但在实际提交中决定了你能不能过。7. 一点复盘做对这道题值钱的不是板子最后聊聊我自己的体会。这道题真正值钱的不是“会写0-1 BFS”或者“会背Dijkstra模板”而是那个建图瞬间的思考方式把一个额外条件翻译成图的边权或状态代价。我复盘的时候给自己总结了三个固定步骤遇到这类题直接套先问自己题目里额外的东西是什么反转、拐弯、换乘都要付出代价。把这个代价塞进图里塞进边权反转还是塞进状态切换拐弯选算法代价是0/1就0-1 BFS代价是非负整数就Dijkstra有次数限制就分层图。这三步走完题基本就解了一半。剩下的一半是细节vis标记顺序、INF范围、重边自环、long long这些也是经验堆积出来的。如果你拿这道题练手建议把0-1 BFS和Dijkstra两个版本都写一遍然后用一组随机数据对拍确保结果一致。对拍是验证理解最有效的方式比只看题解强得多。另外一个扩展方向把反转成本改成“每反转一条边后续所有边的基础成本翻倍”这种奇怪条件——那就是动态规划与最短路结合的问题了但核心还是那个“状态展开”的思路。理解到这层这道题的收获才算真正装进了脑子里。