正常的广搜就是一个起点,像树一样按层先法遍历
今天我们要学习的是多源广搜.

什么是多源dfs

顾名思义,从多个起点开始搜索,也是求最短路的一种方法.

什么时候适用?

个人认为是起点不确定,而且终点有多个的情况,

此时终点是确定的,因此只要同时计算,最后每个起点都会被遍历到,得到的就是最短路了

例题1:

给定01矩阵,求每个0到最近的1的距离.

例题2:

有 n 个城市，编号为 1 到 n，城市之间通过 m条无向道路连接，每条道路的边权为 1，对于一个城市的繁华度是该城市所连接的道路数量。
我们将每个城市的繁华度列出并去重后，从小到大排序得到 $a_1​,a_2​,…,a_k$​，现在将所有繁华度为 $a_i$(1≤i≤k) 的城市称作 i 级城市。
Bingbong 现在需要你帮助他回答对于任意编号为 x(1≤x≤n) 的城市，从该城市出发，前往比该城市级别更高的城市的最短路径长度，或报告无法到达。

注意：此处 k 级城市为最高级城市。

例题2实现起来可能会有一些麻烦,但是发现一个事情是不存在跨过大繁华度城市达到终点的情况,因此,只要每次从大到小,在路径变短时才需要入队,简化了实现.