★ FEATURED ARTICLE 最近把ABC245G这道题彻底摸透了题目名字叫Foreign Friends核心考点就是标题里说的“带颜色限制的多源BFS”。乍一看这题就是个裸多源最短路给定一堆源点求每个点到最近源点的距离。但仔细读题后才发现麻烦全在“带颜色限制”这四个字上——目标源点的颜色必须和出发城市不同否则距离再近也无效。为了说清楚这个题我会先拆解题意和朴素做法为什么超时然后讲多源最短路的基本套路再重点展开“双状态Dijkstra”这种处理颜色限制的思路最后给完整代码和我在实现中踩过的坑。如果你正在准备AtCoder、Codeforces这类比赛或者面试碰到“多源最短路 附加过滤条件”的变种题这篇文章可以直接参考。1. 题目拆解Foreign Friends到底问什么1.1 题意还原题目给了N个城市、M条双向道路每个城市属于一个国家用颜色值A[i]表示。另外有K个城市被标记为“有外国朋友的城市”换句话说这K个城市是候选终点。真正的问题是对于每一个城市i求从i出发到某个“有外国朋友”的城市j的最短距离并且要求j的国家编号不等于i的国家编号也就是A[j] ! A[i]。如果找不到这样的j输出-1。这个限制条件就是标题里“颜色限制”的含义。如果不看后半句这题就是一个标准的多源最短路把K个foreign城市全部塞进队列跑一遍BFS或Dijkstradist数组一出来答案立刻有了。但加了“颜色不同”这个条件后直接跑一遍多源最短路是不够的——因为你没法保证城市i取到的最近源点j一定和i不同色很可能i的最近foreign city恰好和i同属一个国家此时这个距离就必须被丢弃改找次优的异色候选。1.2 为什么不能每个点单独跑最短路有的读者第一反应是那我对每个城市i单独跑一遍Dijkstra搜到一个异色foreign city就停不就行了逻辑上没问题复杂度上直接爆炸。最坏情况下每个点都要跑一次全图规模的最短路整体复杂度是O(N * (M log N))。在N和M都可以到2×10^5这种量级时这意味着大约要执行4×10^10量级的操作跑几分钟都未必能结束。所以核心矛盾在于既要利用多源最短路把“所有点到最近源点”的问题一次性算出来又得额外满足“异色”这个排斥条件。普通单状态的最短路对于每个点只保留唯一最优信息一遇到“这个最优被禁用了”就无从下手。2. 多源BFS/最短路基础把起点打包丢进队列2.1 朴素多源最短路的做法先复习一下多源最短路。所谓的多源BFS实际上就是把单源BFS的初始化从“把起点i的距离设为0”改成“把多个起点的距离全部设为0并一起入队”。在无权图上队列里逐层扩展先被访问到的点一定获得最短距离。在带权图上则改用优先队列就是多源Dijkstra。无论哪种写法核心思路都一致多个源点并行向周围扩散每个点最终记录的是“离我最近的源点有多远”。这个技巧本身非常常用。打个比方可以把每个foreign city想象成一个品牌连锁店的门店。多源最短路要回答的问题是每个小区离最近的门店有多远所有门店同时开门营业先把周围一圈“占领”掉然后一圈一圈往外扩展。某个小区第一次被覆盖时给它记下距离的那个门店就是离它最近的门店。2.2 颜色限制带来的新问题现在把颜色限制加进来。假设门店分两种品牌红色和蓝色而我们要求每个小区必须找一家“和自己小区所属品牌阵营不同”的门店。这时候普通多源扩散就有问题了某个红色小区旁边有一家红色门店距离只有2又有一家蓝色门店距离是5。普通多源最短路会告诉这个小区最近门店距离2。但这个距离2对应的门店是红色的和小区同色不能用。真正答案是5。如果只用一个dist数组这个信息就丢了。我们需要在每个点上额外记录最近源点的颜色是什么如果最近的源点颜色恰好等于出发城市颜色那还得有第二个候选——一个颜色不同、距离次优的源点。于是很自然的想法是每个点维护两个状态一个是最优源点一个是“颜色与最优源点不同”的次优源点。这就是这道题的题眼。3. 双状态Dijkstra维护不同颜色的最优解3.1 状态设计的核心思想对于每个城市v我们维护两个状态dist0[v]到v的最近foreign city的距离。col0[v]这个最近foreign city的颜色。dist1[v]到v的、颜色与col0[v]不同的最近foreign city的距离。col1[v]这个次优源点的颜色。dist0[v]一定小于等于dist1[v]而且col0[v]一定不等于col1[v]。注意dist1[v]代表的不是“全局次优源点”而是“和最优源点颜色不同”的候选里距离最小的那个。这是整个算法的关键差异。有了这两个状态回答任意城市i的答案就很简单了如果col0[i] ! A[i]说明最优源点颜色不等于出发城市颜色答案就是dist0[i]。如果col0[i] A[i]说明最优源点被禁用那就用col1[i]对应的dist1[i]它就是所有异色源点里最近的距离。如果连col1[i]都不存在说明没有异色源点答案-1。这里有个容易想不明白的点为什么维护两个不同颜色的状态就够用直观解释是每个点最终只需要排除一种颜色——它自己的颜色A[i]。两个候选颜色不同意味着无论排除哪个颜色剩下那个候选一定是“未被排除”的最近源点。前者被禁用了就用后者如果两个都没被禁用就用距离更小的那个。3.2 松弛规则到底怎么写双状态Dijkstra的难点在于松弛时怎么更新。传统Dijkstra里一个点只会被更小的距离更新这里每个点有两个槽位更新逻辑变成分类讨论假设当前从优先队列里取出的状态是(d, c)表示到达当前点u的距离为d、源点颜色为c。现在要通过边(u, v, w)去尝试更新v新状态是(d w, c)。更新v时先看颜色c和v的col0[v]是否相同如果c col0[v]说明新状态和当前最优源点来自同一种颜色。此时只需比较距离如果d w dist0[v]就更新dist0[v]。如果c ! col0[v]说明新状态的颜色与最优源点颜色不同它应该去竞争dist1[v]这个槽位。只有d w dist1[v]时才更新dist1[v]和col1[v]。不管更新了哪个槽位更新后都需要检查一次不动式必须始终保持dist0[v] dist1[v]。如果dist1[v]被更新后反而小于dist0[v]就把两个状态交换一下确保dist0始终是最小的那个状态。最后只要更新成功就把(v, d w, c)重新压入优先队列因为v的状态变了它可能继续松弛它的邻居。这里有一个实现细节容易写错很多人在颜色c col0[v]时只更新dist0[v]但忘记dist0[v]更新后仍然要维持dist0 dist1。其实这个场景下不需要额外处理因为dist0本来就小于dist1更新只会让dist0更小不会破坏大小关系。真正需要交换的只发生在更新dist1且新dist1更小的时候。3.3 正确性论证两个状态为什么够要说服自己这个算法是靠谱的可以这样想。假设到达某个点v的foreign city源点集合为S其中每个源点s都有一个距离dist(v, s)。算法希望在S里维护两个状态最优状态s0以及颜色不同于s0的距离最小状态s1。这相当于在S里按照“颜色分组”每组只留下一个距离最小的代表然后从这些代表里挑距离最小的两个且要求这两个代表的颜色不同。为什么挑两个不同颜色的代表就够了因为最终过滤条件只有一个排除出发城市i的颜色A[i]。如果s0的颜色不等于A[i]那么s0就是全局最短也就是答案如果s0的颜色等于A[i]由于s1的颜色不同于s0所以s1的颜色必然不等于A[i]而在所有异色源点里s1又是距离最小的。答案就是dist1[i]。证明的关键在于Dijkstra算法的贪心性质保证了dist0和dist1在被弹出时已经确定了最终值。这和普通Dijkstra的证明思路一致只是这里我们维护了“两种颜色分组下的最优值”。每条边在更新时只会把一个点推向更优的状态优先队列不断取出当前最小状态进行扩展最终收敛。这个“选出最优和它与另一个分组之间异色的次优”的思路和生成树问题里的“次小生成树”有异曲同工之处都是通过维护第二个约束条件下的候选来打破单最优的限制。4. 代码实现和踩坑记录4.1 完整C代码下面给出我调试通过的完整实现。这段代码以Dijkstra实现多源最短路所以即使题目边权不为1也能直接过如果边权全为1可以把优先队列换成普通队列复杂度降低一个log。#include bits/stdc.h using namespace std; using ll long long; const ll INF (1LL 60); struct Edge { int to; ll w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin N M K; vectorint A(N); for (int i 0; i N; i) { cin A[i]; } vectorvectorEdge g(N); for (int i 0; i M; i) { int u, v; ll w; cin u v w; --u; --v; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorll dist0(N, INF), dist1(N, INF); vectorint col0(N, -1), col1(N, -1); priority_queuetuplell, int, int, vectortuplell, int, int, greatertuplell, int, int pq; auto upd [](int v, ll d, int c) - bool { if (col0[v] c) { if (d dist0[v]) { dist0[v] d; return true; } } else { if (d dist1[v]) { dist1[v] d; col1[v] c; if (dist1[v] dist0[v]) { swap(dist0[v], dist1[v]); swap(col0[v], col1[v]); } return true; } } return false; }; for (int i 0; i K; i) { int x; cin x; --x; if (upd(x, 0, A[x])) { pq.push({0, x, A[x]}); } } while (!pq.empty()) { auto [d, u, c] pq.top(); pq.pop(); // 过期状态直接跳过检查取出的状态是否等于u当前的某个有效状态 if (col0[u] c) { if (d ! dist0[u]) continue; } else if (col1[u] c) { if (d ! dist1[u]) continue; } else { continue; } for (const auto e : g[u]) { if (upd(e.to, d e.w, c)) { pq.push({d e.w, e.to, c}); } } } for (int i 0; i N; i) { ll ans -1; if (col0[i] ! -1 col0[i] ! A[i]) { ans dist0[i]; } else if (col1[i] ! -1 col1[i] ! A[i]) { ans dist1[i]; } cout ans (i N - 1 ? \n : ); } return 0; }4.2 实现细节和常见错误我在调试这题的时候至少犯过三个错误写出来供参考。第一初始源点的处理。K个foreign city作为源点时距离都是0颜色就是它们自己的A值。这里要注意upd函数会把新源点当成最优状态存入dist0/col0。如果题目允许同一个城市多次出现在foreign列表里upd会自动去重不会重复push。越界问题也要小心读入的foreign城市编号需要先减1。第二优先队列里的过期状态判断。Dijkstra中同一个点可能被尝试更新多次但只有状态真正变成了该点当前的dist0或dist1才需要扩展。我写的检查逻辑是取出(d, u, c)后如果c等于col0[u]那么d必须等于dist0[u]否则这个状态已经过期跳过如果c等于col1[u]类似。如果c既不是col0也不是col1那更是早就被淘汰的状态直接跳过。很多人在双状态Dijkstra里漏掉这个检查会导致队列里堆积大量无效状态虽然不一定会WA但会显著拖慢运行速度。第三交换时别漏掉颜色数组。upd函数更新dist1后如果发现dist1比dist0小要同时交换dist和col两组数组。只交换距离不交换颜色或者交换顺序写反都会让整个状态匹配错乱。我刚开始就把swap(col0, col1)写在swap(dist0, dist1)前面结果答案全乱。这种错误很隐蔽因为小数据可能恰好蒙对大数据才暴露。还有一个细节是INF的选择。我习惯用(1LL 60)因为边权可能很大如果用常见的1e9可能会被后续加法顶破导致int溢出或ll溢出。1LL60在这个数据范围内足够安全。5. 同类题型和扩展思路5.1 从两个状态推广到k个状态这道题只排除一种颜色所以每个点维护两个状态就够了。但如果你遇到题目要求“找到距离最近的、颜色与出发城市不同的源点”本质上就是一个排除条件。一旦排除条件变成多个比如要求终点颜色不等于列表里的任何两种颜色那每个点维护的状态数量也要对应增加。更一般性地看这种“多源最短路 分组过滤”的问题可以用“每个点维护若干不同分组的最优状态”来解决。状态数量一般等于“需要排除的分组数量 1”。如果分组数量很小比如小于等于3那直接扩展成3状态Dijkstra即可如果分组数量很大那就需要另想办法比如按照颜色分块处理或者用线段树合并。这类变种题里最经典的模型是有若干个商店商店有不同的类别每个家庭需要找到距离最近的、类别不等于自身的商店。本质上就是一个多源最短路 类别约束的问题ABC245G就是这类模型的直接代表。5.2 边权为1时的BFS写法如果题目保证所有边权都是1那么优先队列可以退化为普通队列。Dijkstra之所以需要优先队列是因为要按距离大小顺序扩展如果边权一致BFS天然的按层扩展顺序就是正确的。把priority_queue换成queuepop变成从队首取push放到队尾其余逻辑完全不变复杂度从O((NM)logN)降为O(NM)。我曾在测试时用随机数据对比Dijkstra版和BFS版距离数组完全一致。实际比赛里如果看到题目是普通图且边权为1可以放心用BFS代码更短常数更小。但在没搞清边权范围之前Dijkstra版本更稳妥。5.3 一个需要警惕的细节有的题解会把“次优源点”理解成“全局距离第二小的源点”然后直接维护一个全局次优点。这是错的。全局第二小的源点可能和全局最优源点同色那么当出发城市颜色等于这个颜色时两个候选都被禁用了。也就是说这里维护的不是“距离第一、第二”而是“颜色不同的两个分组里各自距离最小的代表”。这个差别是这道题最容易踩的思维陷阱。画个例子就明白了假设某个城市最近的两个源点都是红色距离分别是1和2蓝色源点距离是5。全局次优是红色距离2但它和最优同色如果出发城市是红色这两个候选全部作废正确答案应该是蓝色距离5。所以维护两个不同颜色的候选才真正覆盖所有可能。5.4 从题目到实际应用的一点联想这种“带限制的多源可达/最短路”在真实场景里也有对应。比如地图导航里用户想找最近的加油站但排除掉自己当前所在品牌的加油站或者外卖平台找“非本连锁品牌的最近门店”。这种需求本质上是既要多源广播所有候选点的距离信息又要在最终查询时应用一个动态的过滤条件。算法竞赛题往往是现实问题的抽象。ABC245G把这个问题抽象成了一个漂亮的图论题而双状态Dijkstra这种“多存一个异色最优候选”的思路在系统设计里也可以迁移——比如需要按类别维护TopK结果时每个节点只存K个不同类别的代表值就够用了。回到这题本身我最后想强调的实操经验是拿到多源最短路变种题先画出“过滤条件有几个”再决定每个点维护几个状态。一个过滤条件对应两个状态两个过滤条件对应三个状态以此类推。这个规律虽然朴素但在很多题里都适用。ABC245G之所以经典就是因为它把一个简单的多源最短路通过颜色限制升级成了需要“次优异色候选”的思维题。把这个题吃透再遇到类似限制条件就很少会卡住了。
阅读完成 · 觉得有帮助？
