似乎是经典套路?
先不考虑颜色限制,那么就直接把 \(l\) 个关键点当作起点跑多源最短路就行了。
现在考虑颜色限制,有一种暴力的想法是枚举所有颜色,只把这种颜色的点当作起点,然后跑dijkstra
,然后更新颜色不为这个的终点。
发现这样终点就被更新了很多次,考虑优化。
考虑枚举颜色的每个二进制位,把所有特殊点这一位上颜色是 \(1\) 的加入起点,跑最短路,更新所有终点中这一位上颜色是 \(0\) 的终点,然后倒过来,把所有特殊点这一位上颜色是 \(0\) 的加入起点,跑最短路,更新所有终点中这一位上颜色是 \(1\) 的终点。
由于两个颜色不同一定至少有一个二进制位不同,因此上述算法可以保证所有终点都被颜色不同的起点更新到。
复杂度 \(\mathcal{O}(m\log n\log k)\)。