图

最短路

• 边权均为 的无向图上，最短路上的节点的 deg 总和是 量级的

证明

考虑最短路上的不相邻的任意两个节点，这两个节点之间不可能有边。 考虑最短路外的任意一个节点，如果它与四个最短路上的阶段均有连边，也会存在矛盾  如图，红色路径一定比黑色路径短 所以设 是最短路上的节点数量。我们有最短路上的所有节点的度数和不大于 ，是 量级的。

二进制

枚举子集

for(int T = S; T!=0; T=((T-1)&S))