关于单位权图最短路的一些小思考
单位权图
每条边权值都为 \(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\),可优化复杂度。