CF1941G

__vector__ · 2024-03-13 15:04:24 · 题解

赛时因为这题没有 AK，有点遗憾。
赛后写了个朴素分层图做法 TLE on test47，参考了 @Iceturky 的代码后 AC，本题解大概是我对 @Iceturky 代码的理解。

做法

首先，有一部分普通的暴力分层图是错的，原因，但很神奇的是它们都过了 pretests，虽然最后死于 FST。

显然，同一种颜色的边在最优路径上都是连续的。

所以说，假设目前到达了第 i 个点，且上一个边颜色是 j，那么我们可以在任意颜色为 j 的边上瞬移。

也就是说，我们主要关心两个变量：当前在哪个点，到达当前点的上一条边的颜色。

感觉瞬移有点难处理，按上述定义建立分层图很容易寄（如果有分层图做法不会寄，希望有人告诉我）。

于是干脆将每个颜色都建成一个点，反正相同颜色可以互相瞬移。

对于每个点，它都可以进入它的所有的边的颜色对应的连通块。就是说对于每个点 i，设其所有边的颜色的集合是 s，那么 i 和 s 中每个元素连无向边。

最后，不难想到最优路径中，每个点在上述连边状态下都会访问一次自己所在的连通块节点，所以最后 b 到 e 最短路长度除以 2 就是正确答案。