首先可以发现,如果有a,b,c三个点,且a向b和c连边,b向c连边,那么此时a直接走到c一定比以b作为中间结点更优 开始将维护数组v[i],v[i]里面存了所有二进制第i位为1的数的编号那么可以构造一个DAG,比如刚开始的时候枚举a[1]的所有的1位,然后直接把v[i]里面的所有点的最短路更新为1到它的距离。然后让新的点入优先队列。维护一个优先队列让距离小的优先更新,而每个v[i]最多被访问一次,即每个点到1的最多距离最多只会被更新一次 #include <bits/stdc++.h> #define N 100010 #define ll long long //#define ...