企业官网建设流程全解析

题目名是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或者Dijkstra：dis[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 + w，newBalance = 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 { vector<ll> costs; vector<ll> balances; }; struct HeapNode { ll cost; int u; ll balance; bool operator<(const HeapNode& other) const { return cost > other.cost; // 小顶堆 } }; bool dominated(const vector<ll>& costs, const vector<ll>& 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(vector<ll>& costs, vector<ll>& balances, ll c, ll b) { // 先检查新状态是否支配已有状态，删除被支配的 vector<int> toDelete; for (int i = 0; i < (int)costs.size(); ++i) { if (c <= costs[i] && b >= balances[i]) { toDelete.push_back(i); } } if (!toDelete.empty()) { vector<ll> 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, vector<vector<Edge>>& g, int s, int t, ll L, ll R) { vector<NodeState> states(n + 1); priority_queue<HeapNode> 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、w=10，v到u有条边delta=+1、w=10，你在u和v之间来回走一圈，耗时变成20，平衡值回到原点，这种状态显然会被已有状态支配，直接扔掉。所以这类回环路径不会导致状态爆炸，但它确实会在扩展时消耗一定时间。如果图上这种双向回环边特别多，建议预判一下：对于耗时相同的两条相反边，可以直接简化为一条零环，不用真的去跑。

4.3 初始状态与边界条件的处理

起点初始状态是(0, 0)，这个没有争议。但终点判断要注意：Dijkstra按用时从小到大弹出状态，如果终点第一次被弹出，那时候的耗时就是最小答案。这里有一个小坑，就是可能存在多条到达终点的路径，其中一条耗时较短但平衡值已经非常接近边界，另外一条耗时较长但平衡值非常安全。由于支配判断只发生在同一节点，终点也需要维护状态列表。如果删掉了终点上某些状态，可能导致你丢失一条后续还要继续扩展的路径（如果终点还有出边且题目不要求必须停在终点，而是求经过终点的某条路的耗时，那你就要小心了）。我建议在代码里把终点和其他节点一视同仁，不特殊处理，这样最稳妥。

4.4 处理离散化与超大平衡值

有朋友问过我：为什么不把平衡值离散化之后再跑普通分层图？理论上可以，但离散化的粒度很难把握。如果按所有delta值做前缀和离散化，状态量是O(n * 可达平衡值数)，而这个数量在最坏情况下依然会达到O(n * L)，和直接开数组没本质区别。帕累托前沿写法的优势在于它把“同节点内的大量平衡状态压缩成少量非支配状态”，压缩是自动完成的，不需要预先知道平衡值的分布。

我实测过一组数据：n=1e5，m=2e5，delta在[-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赛场上留给你证明算法正确性的时间往往很少，与其在写完之后反复检查，不如在动笔之前就把“支配”这层逻辑在纸上推演明白，这才是这道题真正的胜负手。