首页 > 其他分享 >ABC245G

ABC245G

时间:2024-01-18 14:13:47浏览次数:26  
标签:终点 颜色 短路 所有 更新 ABC245G 起点

似乎是经典套路?
先不考虑颜色限制,那么就直接把 \(l\) 个关键点当作起点跑多源最短路就行了。

现在考虑颜色限制,有一种暴力的想法是枚举所有颜色,只把这种颜色的点当作起点,然后跑dijkstra,然后更新颜色不为这个的终点。
发现这样终点就被更新了很多次,考虑优化。

考虑枚举颜色的每个二进制位,把所有特殊点这一位上颜色是 \(1\) 的加入起点,跑最短路,更新所有终点中这一位上颜色是 \(0\) 的终点,然后倒过来,把所有特殊点这一位上颜色是 \(0\) 的加入起点,跑最短路,更新所有终点中这一位上颜色是 \(1\) 的终点。

由于两个颜色不同一定至少有一个二进制位不同,因此上述算法可以保证所有终点都被颜色不同的起点更新到。
复杂度 \(\mathcal{O}(m\log n\log k)\)。

标签:终点,颜色,短路,所有,更新,ABC245G,起点
From: https://www.cnblogs.com/cooltyl/p/17972377

相关文章

  • [ABC245G] Foreign Friends 题解
    [ABC245G]ForeignFriends题解想法考虑所有颜色相同的弱化版。这种情况下,只需要把所有特殊点都推入队列之后跑多源Dijkstra即可。思路正解与上述做法大致相同。如果有颜色限制,那么可以考虑这个神仙思路:把所有特殊点的颜色用二进制表示,对于每一位,这一位是\(0\)的特殊......
  • [ABC245G] Foreign Friends
    ProblemStatementThereare$N$peopleand$K$nations,labeledasPerson$1$,Person$2$,$\ldots$,Person$N$andNation$1$,Nation$2$,$\ldots$,Nation$......
  • ABC245G题解
    似乎是经典套路?先不考虑颜色限制,那么就直接把\(l\)个关键点当作起点跑多源最短路就行了。现在考虑颜色限制,有一种暴力的想法是枚举所有颜色,只把这种颜色的点当作起点,然......