关于单位权图最短路的一些小思考
单位权图
每条边权值都为 \(1\) （或者全部相同也行）的图。
最短路
显然，单位全图的最短路不会经过同一个点，所以，跑单位权图的最短路要用 BFS。
所以我们得到一个处理单位全图的性质 \(1\) ：用一个标记数组取标记哪个点有没有被走过，如果没有就标记并加入到队列，有显然就跳过。
优化
我们要考虑几种情况：
\(n\) 和 \(m\) 都是正常数据
直接像上面一样跑。
\(n\) 正常，\(m\) 很大
如 \(1\leq n\leq 10^5,1\leq m\leq \frac{n(n+1)}{2}\)
例题：ABC319G
因为 \(m\) 很大，所以给的是反图。这种请况我们把标记数组改为 \(set\)（链表也行） ，边集也改为 \(set\)。
这样在跑图时可以遍历标记 \(set\) 并判断有没有在边集 \(set\) 里出现，这样有什么好处？
数组标记时，每次遍历都是 \(O(n)\) 的，但是 \(set\) 可以支持删除和 \(O(size)\) 遍历，反图边很少，所以复杂度很少。
\(n\) 和 \(m\) 都很小，但是要跑很多遍
如 \(1\leq n,m\leq 2000\)，要跑 \(n\) 次最短路。
我们将 \(set\) 改为 \(bitset\) ，判断标记 \(set\) 并判断有没有在边集 \(set\) 里出现，在 \(bitset\) 就是两个取 \(and\)，遍历复杂度更小，且判断少一个 \(log\)。
总结
-
用一个标记数组取标记哪个点有没有被走过，如果没有就标记并加入到队列，有显然就跳过。
-
对于一些情况，标记和边集改为 \(set\)，可优化复杂度。