普通快乐
题目大意:这是一张 n 个点 m 条边的连通图。这张图上面有 k 个奇葩点。保证没有重边和自环。 现在要求你从其中任意一个奇葩点开始走,走到除了这个奇葩点以外的最近奇葩点。 问选择哪一个奇葩点开始走,路程最小。
暴力做法,对每一个奇葩点都跑一边dij或者spfa
考虑优化:(来自Aswert大佬做法)
你考虑对每一个点dij的时候,如果发现我们遇到的这个点就是奇葩点,就停止
因为我们第一次搜到他,无论是哪个点,距离一定是最小的
再加上快读优化,就过了,暴力碾标算
1 | #include <bits/stdc++.h> |
正解:二进制拆分
考虑两个点集S1和S2之间的最短路,我们可以跑一次最短路求出来。
具体可以新建虚拟源点s和虚拟汇点t,s和S1的每个点之间连一条零边,t同理。
那么这一次最短路就相当与求出了|S1|×|S2|对关系之间的最短路最小值。
还可以继续优化
通过二进制分组,我们完全可以使复杂度优化到
枚举顶点标号的二进制的每一位,如果这一位为1,那么把这个点分到S1,否则分到S2。
为什么不能是只跑一位?因为只跑一位可能会少一些情况,在二进制下,很神奇的就不会漏下情况
1 | #include <bits/stdc++.h> |