传送门:https://ac.nowcoder.com/acm/contest/6885/E

题意：给你n个点，每个点有点权。两个点之间有一条边当且仅当 a[i] & a[j] != 0.边权大小为 lowbit(a[i] & a[j]).求 1 -> n 的最短路

思路：

对于位运算，显然我们可以按位统计每个位上有哪些点。接下来介绍几种方法来求最短路.

方法一:Dijstra + 动态删边(比较取巧)

显然让我们朴素的跑Dijstra 最多是有 n^2 个边。复杂度不可接受.但是按位拆分之后，每个位上最多n个点。那么最多 n log n 个点。

那从 1 号点开始，从二进制低位到高位，遇到位为1的，拓展所有 同集合里的所有点 然后再删除掉这些点。有了删除的操作，我们最多拓展 n logn 次。复杂度就有了保证。

正确性不显然.

方法二:暴力多趟并查集

将每个二进制位上出现过1的点进行分组。将得到32个分组。对于每个分组他们两两之间任意互达,代价为 1 << pos.

我们贪心的二进制位置从小往大进行并查集合并。直到合并到 1 和 n 连通。设能够使得1 , n 连通的最低位置为K。

那显然的一点是: 代价 1 << k 是必须花费的。但是 0 ~ k - 1 这些位置上的花费无法直接确定

关键来了：既然 1 << k 是必须花的，那么我们不妨花费 1 << k 的代价将 集合Sk 中的点都合并.再在 0 ~ k - 1 范围内从小到大贪心的合并并查集。如此往复即可。

最多32趟。复杂度为：

方法三:建图思维,虚点法(最优，最有普适性)

将这个问题抽象一下：你现在有n个点，m个集合。每个集合有若干个点。同集合内的元素是互达的，代价为W_m。现在问你从1 ~ n 的最短路。

方法：建立虚点。

要实现 [同集合内的元素是互达的，且代价为W_k] 的功能。我们可以 建一个虚点 n + k.代表这个集合的中转站. 建边的时候建立双向边：去 花费 W_k , 回 花费 0.  这样功能就实现了。

接下来对每个集合建虚点跑最短路即可。

最多nlogn条边。n个点.还是一定要注意边数组开到位。