运行 BFS 寻找从图的底部到顶部的最短路径

Question

我正在尝试解决一个有限制的任务：\$1 \le B,L,S \le 100 000\$。为此，我从图表底部的每条边使用 BFS，并且运行 BFS 直到我们达到 y=0。但是，当运行在编译器中编译代码时，出现超时错误。为什么我会收到 TLE 错误，我要更改此代码中的哪些内容才能通过？

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int bfs(const vector< vector<int> > &g, pair<int, int> p)
{
queue <pair<pair<int, int>, int> > que;
vector< vector<bool> > vis(100000,vector<bool>(100000,false)); //visited
int x, y, k = 0; //k = distance
pair <pair<int, int>, int> next, start;
pair <int, int> pos;
start = make_pair(make_pair(p.first, p.second), 0);
que.push(start);
while(!que.empty())
{
    next = que.front();
    pos = next.first;
    x = pos.first;
    y = pos.second;
    k = next.second;
    que.pop();

    if (y == 0) {
        return k;
    }
    if((g[x+1][y] == 1) && (vis[x+1][y] == false))
    {
        que.push(make_pair(make_pair(x+1, y), k+1));
        vis[x+1][y] = true;
    }
    if((g[x][y+1] == 1) && (vis[x][y+1] == false))
    {
        que.push(make_pair(make_pair(x, y+1), k+1));
        vis[x][y+1] = true;
    }
    if((g[x-1][y] == 1) && (vis[x-1][y] == false))
    {
        que.push(make_pair(make_pair(x-1, y), k+1));
        vis[x-1][y] = true;
    }
    if((g[x][y-1] == 1) && (vis[x][y-1] == false))
    {
        que.push(make_pair(make_pair(x, y-1), k+1));
        vis[x][y-1] = true;
    }
  }
}

int main()
{
int B,L,S,x,y, shortestDist = 1234567;
cin >> B >> L >> S;
vector< pair <int, int> > p; //stones in the first row
vector< vector<int> > g(B, vector<int>(L,0));
for(int i = 0; i < S; i++)
{
        cin >> y >> x;
        g[y][x] = 1; // stone = 1, empty = 0
        if(y == B-1)
            p.push_back(make_pair(x, y));    
}

for(int i=0;i<p.size();++i)
     {
        shortestDist = min(shortestDist,bfs(g,p[i]));
     }
cout << shortestDist + 2 << "\n"; //add 2 because we need to jump from shore  to river at start, and stone to river at end
return 0;
}

Answer 1

您的方法存在两个问题，导致复杂度为 O(B*(B*L+S))。

第一个问题是，如果整个第一行都装满了石头，那么在最坏的情况下你会运行 bfs B 次。你有 S 块石头，每块石头最多有 4 个邻居，因此每次调用 bfs 都会在 O(S) 中运行，但是你做了 B 次，因此你的算法将需要一些关于 O(B* S) 操作 - 我确定问题的作者注意了这个运行ning 时间的程序会超时（毕竟至少有 10^10 次操作）。

这个问题的一个可能的解决方案是启动 bfs，第一行的所有石头都已经在队列中。通过向图中添加一个新顶点并将其连接到第一行中的石头，也可以达到具有多个起点。由于您使用的数据结构，第二种方法对您的实施来说并不那么容易。

而这个（数据结构）是你的第二个问题：你有 S=10^5 elements/vertices/stones 但使用 B* L=10^10 个内存单元。大约2G内存！我不知道这个问题的内存限制是多少——太多了！初始化 B 次总共花费 B* B*L 次操作。

更好的方法是使用像 adjacency list 这样的稀疏数据结构。但要注意在 O(S^2) 中填写此数据结构 - 使用一组 O(SlogS) 甚至 unordered_set O(S) 运行ning 次。

运行 BFS 寻找从图的底部到顶部的最短路径

Running BFS to find shortest path from bottom to top of a graph

c++

graph

breadth-first-search