最近在刷AtCoder的题目清单做到ABC245G“Foreign Friends”这道题说实话第一次提交的时候挂得很惨。题面讲的是多源BFS但偏偏加了一条“终点颜色不能和起点相同”的限制导致朴素做法直接失效。把思路理顺之后发现解法相当精巧每个点不只要维护一个最短距离还要把“来自哪个颜色的源”一起存下来而且只存两种不同颜色的来源就够了。整道题吃透了对多源BFS和状态设计的理解都会上一个台阶。这篇文章就给同样卡在这道题的朋友梳理一遍从题意到实现的完整过程附带我踩过的几个细节坑。1. 题目本质先读明白“颜色限制”到底限了什么1.1 从AtCoder的题面里提取真实约束ABC245G的原始设定并不复杂有N个城市编号1到N每个城市有自己的颜色可以理解成国籍用C_i表示城市之间有M条无向边边权都是1另外给L个城市作为foreign friends也就是有外国朋友居住的城市。题目对每个城市i提问从i出发走到任意一个foreign friend所在城市j最短要经过多少条边但有一个特殊要求i的颜色和j的颜色必须不同。换句话说要找的是“异色友好点”中离自己最近的一个。这个问题如果放在普通多源BFS里就是所有foreign friends一起当起点跑一遍BFS每个点拿到的dist就是到任意友好点的最短距离。然而一旦要求终点异色事情就变了因为“最近的那个友好点”的颜色可能和起点相同不能作为答案而真正合法的异色友好点可能距离远一点点却同样会被BFS先入为主地覆盖掉。为了后面讨论方便这里先设定一个具体的例子。假设有4个点连成一条链1-2-3-4颜色分别是1、2、1、3。友好点设为1颜色1和3颜色1。注意这两个友好点颜色相同都是1。对2号点颜色2来说最近的友好点是1距离1但颜色1和起点颜色2不同合法答案是1。对4号点颜色3来说最近的友好点是3距离1颜色1不同合法。这个例子体现不出难点。如果把友好点1的颜色改成1友好点3的颜色改成1同时让点2颜色也是1那对点2而言两个友好点颜色都等于它自己颜色虽然距离很近但没有合法答案。这就说明光有“距离最近”还不够必须知道“这个最近距离对应的友好点是什么颜色”。1.2 朴素多源BFS到底哪里会翻车朴素多源BFS只有一张dist表dist[i]表示点i到任意友好点的最短距离。瓶颈在于这张表没有携带“来源颜色”信息。当某个点被第一个友好点更新时它只知道“有一个距离这么近的友好点”却不知道那个友好点的颜色是否合法。之后如果出现了一个异色的友好点哪怕它的距离只多了1也因为dist[i]已被填过而被BFS直接忽略。上面这句话其实就是整道题的题眼。BFS的“先来后到”保证了距离最优但并没有保证“颜色合法”。如果你在跑BFS时把dist当成“最终答案”那就把“距离最优”和“颜色合法”这两个维度混在一起了必然出错。正确的思路是把问题拆成两层第一层仍然是跑多源BFS但保留颜色维度第二层在回答每个点时再利用颜色信息做一次判断。具体怎么做就是下一节的核心。2. 核心思路给每个点存“两条来源记录”2.1 为什么只需要两条记录而不是K条假设颜色总数为K最朴素的想法是枚举目标颜色对所有友好点按颜色分组每组跑一次多源BFS最后对每个点找“不等于自己颜色的组里距离最小的”。这样复杂度是O(K(NM))K大的时候直接爆炸。能不能压缩状态回到问题本身每个点最后需要的是“所有友好点中颜色不等于C_i且距离最小的那一个”。如果我们提前知道每个点的两条信息best0最短距离d0以及这个距离对应的来源颜色c0best1在所有来源颜色与c0不同的候选中最短距离d1以及来源颜色c1。那么回答就很简洁了如果c0不等于C_i答案就是d0如果c0恰好等于C_i说明最短的那个友好点颜色跟自己一样不能用此时c1一定是一个与c0不同颜色的来源因此答案就是d1如果d1不存在说明所有友好点都和c0同色即没有异色的友好点答案-1。为什么“两条”就够了因为最终只需要区分“来源颜色等于/不等于C_i”两种情况。一条记录代表“可能同色”的最短距离另一条代表“与第一条不同色”的最短距离。不管第三条、第四条来源颜色是什么它们顶多在这两类里做比较如果某个第三种颜色真的更优那么它在BFS过程中早就把其中一条记录顶掉了。说得更直白一点只有“最短”和“与最短不同色的最短”这两个信息是决策需要的第三种颜色不会再带来新的决策边界。2.2 双记录怎么在不失距离最优的前提下随BFS传播每一条记录本质上是一条“从某个友好点出发的最短路径”的摘要。当这条路径经过一个点时如果它在这个点上创造了新的记录第一个来源或者第一个异色来源那么它就有必要继续向邻居传播因为邻居可能正好需要这个异色来源来构造合法答案。BFS按距离逐层扩展所以每条记录第一次到达某个点时就是同类记录中最短的一档。对于每个点最多只会有两种颜色的记录进入传播第一次到达的任意颜色以及第一次到达的“不同颜色”。之后第三、第四种颜色即使到达距离也必然不会比第二种颜色更近否则BFS会先碰到它。因此每个点虽然理论上可能被多个友好点“看到”但真正能写进双记录并继续向后传递的每个点最多两次入队。这也保证了整体复杂度仍然是O(NM)而不是O(K(NM))。这里有个容易想岔的地方best1的“异色”是相对于best0来说的不是相对于当前点的颜色C_i。因为在BFS过程中我们并不知道当前点最终会被问什么颜色所以只能用“两种不同来源颜色”来覆盖所有可能。等回答时再根据C_i选取。3. 完整实现BFS松弛过程与代码细节3.1 状态设计队列里必须带颜色因为要区分来源颜色队列元素不能只存点的编号至少需要当前点u来源颜色c。距离可以由数组里对应颜色的记录获得但为了写起来直观也可以把当前距离d一起放进队列也就是三元组(u, c, d)。初始化时把所有友好点入队记它们的dist00颜色col0C[id]。这里有个细节每个友好点本身就是一个“到自己的0距离”的来源颜色当然是自己的颜色。即使这个点最后因为颜色相同不能作为答案它仍然可以作为中转点把信息传递给其他点。在BFS时假设取出的三元组是(u, c, d)接下来遍历u的每个邻居v按下面规则尝试用(d1, c)更新v如果col0[v]还没设置等于-1说明这是第一次有友好点的信息到达v直接设置col0[v]c、dist0[v]d1并把(v, c, d1)压入队列。如果col0[v]已经设置且col0[v]c说明这是一条同色来源距离不可能比之前更优直接放弃。如果col0[v]已经设置且col0[v]!c说明这是一个与col0[v]不同颜色的来源如果col1[v]还没设置设置col1[v]c、dist1[v]d1并入队。如果col1[v]c说明这个颜色已经有异色记录了放弃。如果col1[v]存在且不等于c这就是第三种颜色的来源。在边权为1的BFS中它的距离不会比现有的dist1[v]更短所以可以不更新不入队。严谨起见可以判断一下如果d1 dist1[v]就更新但实际不会触发。关于“第三种颜色不会更短”这一点我再解释一下。BFS是按距离从小到大访问的dist1[v]第一次被某个异色颜色c1设置时它的距离d1已经是“所有非c0来源颜色”中的最小距离。第三种颜色c2如果想到达v它的最小距离d2必然大于等于d1否则BFS会先通过c2到达v从而在设置dist1时选的就会是c2。既然d2d1那么c2无法改善已有的异色记录所以忽略是安全的。3.2 回答每个点时的选择逻辑BFS结束后每个点i可能有0、1、2条记录。回答逻辑可以写成if (dist0[i] ! INF col0[i] ! A[i]) { ans dist0[i]; } else if (dist1[i] ! INF) { ans dist1[i]; } else { ans -1; }这里要特别说明为什么第二种情况不检查col1[i] ! A[i]因为能走到这个分支时必然是因为col0[i] A[i]否则第一个分支就成立了。而col1[i]和col0[i]不同自然col1[i] ! A[i]所以dist1一定合法。如果col0[i] ! A[i]但dist1不存在走第一个分支如果col0[i] A[i]且dist1为INF则没有合法异色友好点输出-1。这个逻辑很关键初学者容易在第二个分支里多写一个颜色判断反而影响理解或引入不必要的分支。3.3 参考代码C17实现下面贴一段我调试通过的实现代码风格偏向竞赛常用写法关键位置都加了注释。#include bits/stdc.h using namespace std; const int INF 1e9; struct Node { int u, c, d; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K, L; cin N M K L; vectorint A(N); for (int i 0; i N; i) cin A[i]; vectorvectorint g(N); vectorint friends(L); for (int i 0; i L; i) { cin friends[i]; friends[i]--; } for (int i 0; i M; i) { int u, v; cin u v; --u; --v; g[u].push_back(v); g[v].push_back(u); } vectorint dist0(N, INF), col0(N, -1); vectorint dist1(N, INF), col1(N, -1); queueNode q; // 所有友好点作为初始源 for (int id : friends) { if (col0[id] -1) { // 防止重复给定同一个友好点 col0[id] A[id]; dist0[id] 0; q.push({id, A[id], 0}); } } while (!q.empty()) { Node cur q.front(); q.pop(); int u cur.u; int c cur.c; int d cur.d; for (int v : g[u]) { int nd d 1; if (col0[v] -1) { col0[v] c; dist0[v] nd; q.push({v, c, nd}); } else if (col0[v] c) { continue; } else { if (col1[v] -1) { col1[v] c; dist1[v] nd; q.push({v, c, nd}); } else if (col1[v] c) { continue; } else { // 第三种颜色按BFS性质不会产生更优更新可忽略 } } } } for (int i 0; i N; i) { int ans -1; if (dist0[i] ! INF col0[i] ! A[i]) { ans dist0[i]; } else if (dist1[i] ! INF) { ans dist1[i]; } cout ans (i 1 N ? \n : ); } return 0; }如果担心图中存在非1边权就不能用这段代码需要把BFS改成Dijkstra并把每个点的两个dist都同时参与松弛。AtCoder原题边权恒为1所以这里问题不大。3.4 关键操作背后的为什么这里补充两个容易忽略的细节。第一个为什么邻接点更新时不比较新距离和历史dist大小因为BFS队列本身按距离非递减出队第一次访问时给出的就是最短距离所以只要判断颜色槽位是否为空即可不需要额外“如果距离更短才更新”。我写的代码在col0[v]-1时直接设置没有比较就是这个原因。如果是含权图就必须保留距离比较否则会错。第二个为什么同色来源直接continue同色来源即使比已有记录短BFS会先走到它所以后续同色不会再更短如果它不是最短保留现有记录即可。“同色来源”和“现有记录”对最终答案的作用是一样的它们的颜色c相同在回答时一起被判定为“等于或不等C_i”因此只需要保留其中距离最短的一条。BFS已经保证了第一条就是最短的同色来源后面同色不用管。4. 边界情况、性能分析与调试心得4.1 最容易踩的边界条件第一个边界所有友好点颜色都相同且某些点颜色也相同。这种情况下除了颜色和友好点不同的点之外其余点大概率没有合法答案。跑完BFS后这些点的dist0存在但col0等于自身颜色dist1不存在于是输出-1。这个逻辑正好正确。第二个边界友好点重复给定。虽然题目可能不会这么给但保险起见初始化时判断col0[id]是否已存在可以避免重复入队。不判也不会导致结果错误但可能让同一个点多次入队虽然每个点只会设置一次col0后面的重复源会直接continue。判重属于防御性写法。第三个边界孤立点。如果某个点没有任何边BFS永远不会遍历到它dist0和dist1都是INF输出-1。注意友好点本身如果就是孤立点它会在队列里但没有邻居它的dist00颜色是自己的颜色回答时如果要求到异色友好点dist1不存在输出-1。这也合理。第四个边界自环和重边。由于是BFS自环会把邻居更新为当前点自己距离d1一定大于现有dist会被跳过重边不过是邻居遍历时重复访问但记录已存在不会造成新的更新。所以不需要特殊处理。4.2 复杂度为什么还是O(NM)每个点有两条记录每条记录在设置后会把对应的v,c,nd入队所以每个点最多入队两次。BFS遍历每条边时对每条边至多检查两次对应两种颜色的记录流经该边。因此时间复杂度O(NM)空间上需要N个点的两组dist和颜色约4N个int完全可控。这里我再说一个常见的疑问如果一种颜色的源到达某个点设置了col0另一种颜色的源到达后设置了col1那么当第三种颜色源的路径经过这个点再往下传时为什么不需要把它再入队因为该点的dist1已经是异色最优第三种颜色的距离不会比dist1短从该点出发到邻居的距离也会比现有异色记录长。邻居如果要使用异色源用该点现有的dist1就够了。如果第三色比dist1短则说明BFS顺序上它应被更早发现不会发生。所以入队两次是足够且必要的。关于“入队两次”的极端场景如果初始有多个友好点颜色不同BFS过程中某个点可能先被A色更新再被B色更新之后C色源距离虽然等于B色但C色与A色不同距离也等于dist1没有改善不入队如果距离更小理论上C色就应该先于B色到达。所以没问题。4.3 我踩过的两个坑第一个坑是初始化时直接设置了dist0[id]0但没给col0赋值导致后面更新时判断col0[v]c恒不成立。这种低级错误写代码时很常见优先把col0设置好再入队。第二个坑是试图在BFS内部就进行“与当前点颜色不同”的判断也就是扩展邻居前先检查c是否需要传给邻居。实际上不对因为路径经过的中间点的颜色不影响合法性合法性的判定只发生在终点。如果在中间就剪枝会把一些合法的中转路径剪掉。正确的姿势是BFS只负责算距离和记录来源颜色答案留到最后统一判断。如果题目改成“中途不能经过与起点同颜色的城市”那情况会完全不同需要在状态里额外记录起点颜色因为中间点的颜色限制依赖起点那就不是这个双记录能解决的了。这里提醒读者区分“终点异色”和“路径禁色”两种限制它们虽然都叫颜色限制但解法天差地别。4.4 从这道题学到的一种通用手法“用两条不同来源的最短记录来覆盖限制条件”这个思路不止适用于这道题。以后遇到“要求最近的目标不能来自某个集合”或“不能与自身属性冲突”的BFS或最短路都可以考虑维护最优解的同时维护一个与最优解来源不同的次优解回答时二选一。关键点在于把“来源”和“答案冲突”的关系搞清楚设计出足够小的状态。这与“次短路”问题思路相近但又不完全一样——次短路要求距离第二小这里的第二记录只要保证来源颜色不同距离并不一定是全局第二小。明白这一点可以避免被“次短”这个直觉带偏。我个人刷下来最大的感受是遇到带限制的多源BFS先别急着写模板把“限制到底发生在判断终点还是判断中途”想清楚远比记住某个代码模板重要。ABC245G真正的难点不在BFS本身而在状态设计。当你意识到每个点只需要保留两条不同颜色的记录时整个代码会变得非常干净。如果你也被这道题卡过希望这篇复盘能帮你把思路捋顺下次再碰到类似限制应该就能条件反射地想到双记录法了。