BFS求距离多源BFS

这个思路采用逆向思维方式不是枚举最短路径判断安全系数而是枚举安全系数判断对应的最短路径是否存在也是分为两部分一部分是如何枚举安全系数另一部分是如何判断只经过安全系数为lim并且连通起点到终点的路径是否存在。

枚举路径中安全系数经过的格子的最小值可以是哪些相当于枚举只经过安全系数为lim的路径路径中经过的格子安全系数全都大于等于lim能否从起点到达终点然后让这个lim尽可能地大。

枚举安全系数

可以直接从最大的开始枚举找到一个符合条件的就可以结束了O(n)

//直接从大到小枚举for(int

imin(dis[0][0],dis[n-1][m-1]);i0;i--){if(check(i))

return

l0,rmin(dis[0][0],dis[n-1][m-1]);while(lr){int

lmid;else

判断路径上的安全系数为lim也就是之前求出来的所有节点的值大于等于lim的连接起点到终点的路径是否存在有多种方法bfsdfs并查集只要判断起点和终点连通就行。

BFS

//通过一次bfs检查能否只经过安全系数大于等于lim的格子从左上角走到右下角bool

check(int

lim){q.push({0,0});memset(visited,

sizeof(visited));visited[0][0]true;while(!q.empty()){pii

q.front();

jj));visited[ii][jj]true;}}return

深搜不行因为涉及到回溯导致每个节点可能访问多次导致深搜的时间复杂度无法控制在O(n^2)内会超时。

int

lim){//初始化并查集每个元素是自己将二维的数组拉成一维的int

x0;for(int