新方法get
法一：我们考虑最终的答案，一定是从某一个关键点 \(A\) 走到另一个关键点 \(B\)，那我们要找一种最短路径，保证中途经过两个关键点，而且能够覆盖所有的关键点对。所以我们考虑把其中一部分关键点作为起始点的下一个点，剩下的关键点作为终点的上一个点，于是我们建立两个虚点\(s\)和\(t\)，从\(s\)出发向第一部分关键点连有向边，从第二部分关键点向\(t\)连有向边，这样从\(s\)到\(t\)的最短路就包含了\(A\)和\(B\)两部分的所有集合点对。然后我们利用事实，若\(i≠j\)，则两者的二进制位一定有一位不同，通过枚举二进制位遍历分组就好了
法二：这就要用到一个比较新的dij的操作了
我们枚举每一条边\((u,v,w)\)，如果我们假设某个关键点\(p\)是所有关键点里面到\(u\)最近的一个关键点，\(q\)是\(v\)到所有关键点中最近的一个关键点，那么显然\(p\)->\(u\)->\(v\)->\(q\)就是一种可能的候选答案。我们枚举所有的边，显然就不会漏掉答案，现在的关键问题是怎么求出\(p\)和\(q\)
这就要用到dij的一种骚操作了，先求\(p\)。我们把所有关键点的\(dis\)初始化为\(0\)，其余的\(dis\)都为正无穷，然后把所有关键点先一次性加入优先队列里面，然后跑dij就可以了。再求\(q\)，这个时候我们在反图上面跑类似的过程就好了
这种方法一般可以用来解决下面的问题：一个图上有若干关键点，求每个点到任意一个关键点的最短距离
标签：dij,二进制位,所有,旅行者,枚举,我们,关键点 From： https://www.cnblogs.com/dingxingdi/p/18078411