CodeForces-2179F Blackslex and Another RGB Walking 题解

设disudis_udisu​为1→u1\to u1→u的最短距离。则若(u,v)(u,v)(u,v)存在则∣disu−disv∣1|dis_u-dis_v|1∣disu​−disv​∣1。证明显然∣disu−disv∣≤1|dis_u-dis_v|\le 1∣disu​−disv​∣≤1否则违背最短路性质。若disudisvdis_udis_vdisu​disv​则1,u,v1,u,v1,u,v三点形成奇环矛盾。证毕。如果构造分层图使得点uuu在第disudis_udisu​层那么每条边都会连接相邻两层的点。于是从点111出发 bfs 求disdisdis然后按照dis mod 3dis \bmod 3dismod3进行染色即可。