CodeForces-2179F Blackslex and Another RGB Walking 题解

· · 题解

设 dis_u 为 1\to u 的最短距离。则若 (u,v) 存在，则 |dis_u-dis_v|=1。

证明：显然 |dis_u-dis_v|\le 1，否则违背最短路性质。若 dis_u=dis_v，则 1,u,v 三点形成奇环，矛盾。证毕。

如果构造分层图使得点 u 在第 dis_u 层，那么每条边都会连接相邻两层的点。

于是从点 1 出发 bfs 求 dis，然后按照 dis \bmod 3 进行染色即可。