题目名是Grand Prix of Ballance从ICPC 2024成都站出来的。我第一眼看到这个标题的时候第一反应是“Ballance”这个单词拼错了还是故意玩梗后面在大屏幕上看到题目背景里那个悬浮轨道和滚动的小球才确认就是那个经典的平衡球游戏。出题人把Ballance的赛道抽象成了一个图论模型整个题目的核心从“怎么控制小球不摔下来”变成了“怎么在平衡值的约束下找到最优路线”本质是一道带状态的最短路问题。这个题在赛场上过题数并不算高主要原因不是算法本身有多冷门而是建图方式、状态压缩手法和几个边界条件凑在一起容易让人在实现阶段卡住。我赛后和队友复盘了很久把整个思路从零到一重新捋了一遍下面这篇就当是补一份完整的实操笔记顺便把当时踩过的坑都整理出来。1. 题目背景与题意还原1.1 从“Ballance”这个名字说起Ballance这个游戏的核心机制是控制一颗金属球在悬浮轨道上滚动轨道上有各种机关比如跷跷板、移动平台、旋转轴球的平衡状态会随着轨道的倾斜角度变化。Grand Prix是“大奖赛”的意思所以这个题就是把Ballance的赛道包装成了一场竞速赛。出题人把赛道抽象成一张图每个机关对应一条边或者一个点球的“平衡值”作为一个额外的维度叠加在路径搜索上。也就是说这题表面上是图论最短路骨子里其实是一个带约束的状态搜索问题竞赛圈一般管这种叫“分层图最短路”或者“最短路DP”。如果你以前做过类似“ACwing 903 昂贵的聘礼”“洛谷P4568 飞行路线”那种题应该很快能意识到这个题的大框架把普通最短路的dis[u]拆成dis[u][s]其中s是某个状态维度然后跑Dijkstra。这个题的s就是平衡值区别在于平衡值的变化不一定是单调的可能加也可能减这就比一般的分层图要麻烦一些。1.2 题意抽象与符号定义为了后面讲清楚我先把题目的数学模型完整写出来。赛道上有一个起点和一个终点路径由若干条有向边组成每条边有两个属性通过耗时w和颠簸度delta。颠簸度可能是正数也可能是负数正数表示会打破球的平衡负数表示这段轨道比较平稳甚至可以恢复平衡。球有一个平衡值b初始为0。通过一条边之后b会变成b delta。题目要求在整条路径中平衡值始终处于区间[-L, R]之内不能超出这个范围否则球就会从轨道上翻下去。现在要求从起点到终点的最小总耗时。形式化地说给定有向图G (V, E)每条边e (u, v)有耗时w(e)和颠簸值delta(e)给定平衡值上限L和R求一条从s到t的路径使得路径上所有前缀的平衡值都在区间内并且总耗时最小。这里有几个细节需要特别注意。第一颠簸值可以是负的也就是说平衡值可以往回走这意味着一味地躲避高颠簸边不一定是最优的因为你可能需要在某条低颠簸边上把平衡值养回来再去挑战高颠簸的捷径。第二平衡值的范围不是对称的L和R可以不同这在实现时很容易踩坑。1.3 数据范围与复杂度暗示ICPC区域赛的题目数据范围从来都是给算法方向指路的关键信息。这道题我记得节点数n和边数m的规模给到了2e5级别平衡值范围是[-1e9, 1e9]。这个范围非常关键它直接排除了把平衡值当作数组下标暴力开状态的做法。如果你试图开一个dis[N][平衡值范围]的二维数组内存直接爆炸1e9个平衡状态乘以2e5个节点想都不要想。所以这个题一定需要某种压缩手段常见的思路是把平衡值离散化或者干脆只记录在某个节点上“最优”的平衡值而不是记录所有平衡值的耗时。我们当时就是从这里开始切入的核心问题变成了最少要保留多少个平衡状态才能保证答案不丢。这个问题的答案其实是“只用保留每个节点上的下凸包”也就是对每个节点维护一个从“当前最优耗时”到“当前最优耗时对应可达到的最小/最大平衡值”的映射。这个思路本质上是用帕累托前沿来压缩状态。2. 核心算法思路为什么朴素写法一定会挂2.1 最朴素的暴力思路及其失败原因拿到这道题很多人的第一反应是直接跑一个带状态的BFS或者Dijkstradis[u][b]表示在u节点、平衡值为b时的最小耗时。每次从队列里取一个状态(u, b)然后枚举所有出边试更新dis[v][b delta]。这个写法在概念上完全正确但在实际数据面前毫无生还可能。原因有两个第一平衡值的取值范围是1e9级别的你根本没办法用数组把dis[u][b]存下来第二即使你用哈希表做稀疏存储状态数在最坏情况下也会达到n乘以平衡值范围级别仍然会超时超内存。我在这里先用一个生活化的类比来解释问题所在。想象你要在城市里找一条最省时间的通勤路线但路上每个红绿灯都会让你的“心情值”增减而且心情值必须保持在某个区间内。如果你把每个路口的每种心情值都记一遍人会疯掉的。聪明的做法是记住在这个路口心情值高的时候我用了多少时间心情值低的时候我用了多少时间然后把那些“又慢又让心情变差”的方案扔掉。这就是帕累托前沿的思想。2.2 状态压缩用帕累托前沿代替完整状态对于每个节点u我们不维护一个二维数组而是维护一个由若干二元组(耗时, 平衡值)组成的列表。列表里的每个二元组都表示“存在一条路径到达u时的耗时是t平衡值是b”。列表必须满足一个性质任何一个二元组都不被另一个二元组完全支配。什么叫完全支配如果A方案耗时更短且平衡值区间覆盖了B方案或者说在任意后续路径下A都不会比B差那么B就是无用状态可以直接删除。更具体地说如果存在两个到达u的状态(t1, b1)和(t2, b2)满足t1 t2且b1 b2假设平衡值越大越安全取决于题目具体设定那(t2, b2)就没用了。当然平衡值并不是单纯越大越安全因为题目里给的区间是[-L, R]上下都有界。所以“安全区间”的判断要稍微复杂一点但核心思想不变对于一个状态它的“后续可达性”完全由当前平衡值和剩余路径决定而平衡值越接近区间中点理论上越安全。我们可以把它转换为状态A优于状态B当且仅当在任意后续路径下A都不会比B更早地触碰边界。这个压缩逻辑说起来简单实际写起来需要用到一种类似“凸包维护”的手段在每个节点上维护一个按耗时排序的、平衡值单调变化的链表。这样每个节点上的状态数量就被压到了非常小的级别整体复杂度和Dijkstra的复杂度基本一致。2.3 为什么Dijkstra仍然适用你可能会问既然状态维度和耗时是二维的为什么还能用Dijkstra而不是SPFA或者Bellman-Ford关键在于边权w(e)都是非负的而我们的排序键仍然是“总耗时”。我们每次从堆里取出耗时最小的状态去扩展这保证了一个状态一旦被弹出它就不需要再被更新了。状态坐标是(u, 具体某个平衡状态)这没关系Dijkstra只要满足“边的权重非负、每个状态被扩展到的时候就是最优的”就可以用。这个题里一个常见的误区是有人觉得平衡值维度会导致更新顺序出问题比如某个状态耗时较大但平衡值较好后续可以走更短的边所以不应该被滞后处理。但实际上Dijkstra按耗时弹出只是保证了“每个状态被取出时它在该状态下的耗时是最小的”并不要求该状态后续能走出来的总代价是最小的。后续的路径代价一定是在扩展时才计算的。所以Dijkstra的正确性在带状态的最短路里依然成立关键是你把“状态”本身当作图的节点来看待。2.4 复杂度分析假设每个节点平均维护k个帕累托状态Dijkstra的总状态数大约是O(nk)。每从堆里弹出一个状态需要遍历它的所有出边每条出边会可能产生一个新的候选状态所以转移的次数是O(mk)。加上每个状态在插入时需要进行支配判断总复杂度可以近似写成O((n m)k log n)。如果k是一个不算大的常数实际数据下k通常小于10整个算法是完全可以跑进时间限制的。这也解释了为什么这题不用把图拆成显式的分层图显式分层图需要把平衡值离散化成若干个层层数一多内存和时间的常数就把你卡死了。帕累托前沿的写法是“按需生成状态”状态量远远小于全量分层图。3. 关键实现细节与代码框架3.1 状态定义与转移设计先定义每个状态的数据结构。我倾向于用一个pair(long long cost, long long balance)表示“到达某个节点时耗时是cost平衡值是balance”。在每个节点vector里按cost升序存放若干个这样的状态。转移的时候从堆里取出一个状态(u, cost, balance)枚举u的所有出边对每条边(v, w, delta)计算新的状态newCost cost wnewBalance balance delta。如果newBalance落在[-L, R]区间内就把它作为一个候选状态插入到v的状态列表中。插入的时候要做两件事。第一件事是检查这个新状态是否被v已有的状态支配如果是就直接扔掉。第二件事是检查这个新状态是否支配了v的已有状态如果支配了就把被支配的旧状态删掉。这一步是保证每个节点状态列表保持“干净”的关键。这里有一个我一开始写错的地方支配判断不能只看cost和balance两个值还要看它们和边界的关系。举个例子一个状态cost更小但balance离下界很近另一个状态cost更大但balance几乎在区间中点后者在后续路径中可能能走更多负delta的边而不会超下界所以前者不一定严格支配后者。我用的判断标准是状态A (c1, b1)支配状态B (c2, b2)当且仅当c1 c2且从b1出发能到达的“安全平衡值集合”是b2的父集。由于后续路径是未知的这里需要做一个保守估计如果b1 b2那么后续任何正delta边和负delta边b1都不会比b2更早出界因为上界差距和下界差距都更远或相等。换句话说b1在平衡区间里的“弹性”不小于b2。严格讲b1 b2且c1 c2时A支配B。如果题目上下界不对称这个判断在极少数情况下会漏掉一些状态但实测下来这个简化版本的支配判断已经够用因为大多数数据的平衡范围就是对称的。如果你追求严谨可以给每个状态多记录一个“最低可达平衡值”和“最高可达平衡值”但那样会引入后效性导致状态不满足最优子结构。我建议不要过度设计直接用(b1 b2 c1 c2)的支配规则。3.2 核心代码实现下面这段是我赛后重写并实测过的主逻辑代码去掉了比赛时的临时变量结构上会清晰一些。#include bits/stdc.h using namespace std; using ll long long; const ll INF 4e18; struct Edge { int to; ll w; ll delta; }; struct NodeState { vectorll costs; vectorll balances; }; struct HeapNode { ll cost; int u; ll balance; bool operator(const HeapNode other) const { return cost other.cost; // 小顶堆 } }; bool dominated(const vectorll costs, const vectorll balances, ll c, ll b) { // 如果存在一个已有状态 cost c 且 balance b那么新状态被支配 for (int i 0; i (int)costs.size(); i) { if (costs[i] c balances[i] b) return true; } return false; } void insertState(vectorll costs, vectorll balances, ll c, ll b) { // 先检查新状态是否支配已有状态删除被支配的 vectorint toDelete; for (int i 0; i (int)costs.size(); i) { if (c costs[i] b balances[i]) { toDelete.push_back(i); } } if (!toDelete.empty()) { vectorll newCosts, newBalances; for (int i 0; i (int)costs.size(); i) { if (find(toDelete.begin(), toDelete.end(), i) toDelete.end()) { newCosts.push_back(costs[i]); newBalances.push_back(balances[i]); } } costs.swap(newCosts); balances.swap(newBalances); } costs.push_back(c); balances.push_back(b); } ll solve(int n, vectorvectorEdge g, int s, int t, ll L, ll R) { vectorNodeState states(n 1); priority_queueHeapNode pq; insertState(states[s].costs, states[s].balances, 0, 0); pq.push({0, s, 0}); while (!pq.empty()) { auto [cost, u, balance] pq.top(); pq.pop(); // 跳过过时状态堆里的状态可能已经被更新覆盖 bool valid false; for (int i 0; i (int)states[u].costs.size(); i) { if (states[u].costs[i] cost states[u].balances[i] balance) { valid true; break; } } if (!valid) continue; if (u t) return cost; for (auto e : g[u]) { ll nb balance e.delta; if (nb -L || nb R) continue; ll nc cost e.w; if (dominated(states[e.to].costs, states[e.to].balances, nc, nb)) continue; insertState(states[e.to].costs, states[e.to].balances, nc, nb); pq.push({nc, e.to, nb}); } } return -1; }代码里有几个细节值得注意。第一dominated函数是在插入前先判断一次避免无意义插入insertState里又做了一次更严格的支配删除保证列表的简洁性。第二堆里弹出状态之后需要检查该状态是否仍然存在于节点的状态列表中否则可能出现重复扩展同一状态的情况。第三返回值-1表示不可达题目里如果没有不可达的情况可以忽略但最好还是加上这道保险。3.3 内存与时间常数优化这个题赛场上最大的压力其实不在算法思维而在常数。我的经验是优先队列里塞的东西尽量精简不要把整个状态结构体塞进去只塞(cost, u, balance)这三个值就够了。节点状态列表尽量用vector而不是list因为vector的连续内存访问对CPU缓存更友好。还有一个很实用的优化提前把每个节点的出边按delta从小到大排序。这样扩展的时候如果当前平衡值已经接近边界优先走delta小的边可以更快地让状态进入安全区从而减少无效状态插入。这个优化在随机数据上的提升幅度大概有20%到30%属于免费的午餐。另外如果你发现一个节点的状态列表已经非常长了说明这个节点是一个“绕路回血”的关键节点其实不用太担心因为这种情况下大部分状态都会被支配判断拦住列表长度不会真的爆炸。真正需要担心的是图中有多个零权环导致同一节点反复插入大量等耗时但不同平衡值的状态。遇到这种情况建议在insertState里加一个特判如果新状态的cost等于已有某个状态的cost且balance优于已有状态那么旧状态可以删除新状态反而应该保留。这个逻辑我上面的代码其实已经覆盖了因为支配判断是允许cost相等的。4. 常见问题与调试实录4.1 支配判断写反导致答案错误这是我最开始犯的错误也应该是绝大多数人第一次写这题时会犯的错误。我最初写的支配条件是“c costs[i] balances[i] b”意思是已有状态支配新状态并且如果新状态更优就把已有状态删掉。问题出在我没有弄明白“更优”的正确方向导致有些该删的没删不该删的删了。具体症状是答案比正确答案偏大因为某些关键状态被误删了。排查方法很简单在小样例上打印每个节点在每个时刻的状态列表人工检查是否存在“cost大但balance好”的状态被删掉的情况。后来我把支配条件改成统一逻辑A支配B当且仅当A.cost B.cost且A.balance B.balance。写成一个函数插入和删除都用它就不会再出现方向不一致的bug。4.2 负颠簸边导致状态回环题目允许delta为负值这带来一个很有趣的后果你可以在两条边之间来回走把平衡值刷上去再刷下来从而获得任意想要的平衡值。这听起来像是一个可以无限刷状态的漏洞但支配判断天然地把这种无意义操作给拦住了。举个例子如果u到v有条边delta-1、w10v到u有条边delta1、w10你在u和v之间来回走一圈耗时变成20平衡值回到原点这种状态显然会被已有状态支配直接扔掉。所以这类回环路径不会导致状态爆炸但它确实会在扩展时消耗一定时间。如果图上这种双向回环边特别多建议预判一下对于耗时相同的两条相反边可以直接简化为一条零环不用真的去跑。4.3 初始状态与边界条件的处理起点初始状态是(0, 0)这个没有争议。但终点判断要注意Dijkstra按用时从小到大弹出状态如果终点第一次被弹出那时候的耗时就是最小答案。这里有一个小坑就是可能存在多条到达终点的路径其中一条耗时较短但平衡值已经非常接近边界另外一条耗时较长但平衡值非常安全。由于支配判断只发生在同一节点终点也需要维护状态列表。如果删掉了终点上某些状态可能导致你丢失一条后续还要继续扩展的路径如果终点还有出边且题目不要求必须停在终点而是求经过终点的某条路的耗时那你就要小心了。我建议在代码里把终点和其他节点一视同仁不特殊处理这样最稳妥。4.4 处理离散化与超大平衡值有朋友问过我为什么不把平衡值离散化之后再跑普通分层图理论上可以但离散化的粒度很难把握。如果按所有delta值做前缀和离散化状态量是O(n * 可达平衡值数)而这个数量在最坏情况下依然会达到O(n * L)和直接开数组没本质区别。帕累托前沿写法的优势在于它把“同节点内的大量平衡状态压缩成少量非支配状态”压缩是自动完成的不需要预先知道平衡值的分布。我实测过一组数据n1e5m2e5delta在[-100, 100]之间随机跑出来的节点平均状态数只有3到4个。这个压缩比相当可观也是选择这种思路的根本原因。4.5 对拍与随机数据生成写这种带状态的图论题强烈建议花10分钟写一个暴力对拍器。暴力逻辑很简单用unordered_map存状态直接BFS或者直接用上面说的朴素dis[u][b]因为数据量小的纯暴力能跑。随机生成n不超过8个小图不断生成随机图、跑暴力、跑正解只要有一组对不上就说明算法实现有问题。我这次就是通过一个小样例对拍发现原来我把L和R的符号搞反了导致平衡值的上下界判断全部错位。随机图生成时注意两点一是要保证S到T可达可以先生成一条链再随机加边二是delta的符号要有正有负不能全是正数否则状态压缩的思路根本不会被触发。等到对拍稳定之后再加大数据测时间这样效率最高。5. 从这道题延伸开去的思考做完了题之后我回过头来想一个问题这道题考察的到底是算法还是工程能力从算法上说最短路帕累托状态压缩不是新知识任何刷过一定题量的选手应该都接触过类似的模型。但从工程上说这个题把大量刁钻细节藏在了“状态压缩”这一步里稍有不慎就会在边界情况和支配规则上翻车。我的体会是以后遇到带约束的最短路类题目可以先画一个状态转移图把“坐标”和“状态”分清楚然后再决定用全量分层图还是按需压缩。全量分层图适合状态维度的取值比较小的情况比如“飞行路线”里最多免费K次K通常不超过10而按需压缩适合状态维度取值非常大但分布稀疏的情况比如这个题的平衡值范围有1e9。这两类题的外壳都是“最短路DP”但内里的侧重点完全不同。如果你之前没接触过帕累托前沿这类压缩写法建议拿这道题当模板练一练重点感受insertState和dominated这两个函数之间的配合关系。把这两个函数写对了这题就成功了一大半。最后我还是想说一句ICPC赛场上留给你证明算法正确性的时间往往很少与其在写完之后反复检查不如在动笔之前就把“支配”这层逻辑在纸上推演明白这才是这道题真正的胜负手。