交上去是T了是吧？是每次循环都memset的问题。
by LG_kemeng @ 2023-12-24 15:07:13
可以考虑一个问题，就是 $vis$ 数组是否必要。经过考虑，发现我们并不需要这样一个不仅没有用处而且每次循环（共1e5此循环）都要完全重置一遍的累赘。 $vis$ 的功能完全可以由 $table$ 直接替代。每次循环重置的操作实在太浪费时间了，导致直接T上天了。
by LG_kemeng @ 2023-12-24 15:09:36
对呀
by kebibulainente @ 2023-12-24 15:09:41
你的代码改完了，在这里，已AC：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,s;
};
int table[505][505];
int n,m,d,j,stx,sty;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
inline bool check(register int x,register int y)
{
return x>=1 and x<=n and y>=1 and y<=m;
}
void bfs()
{
queue<node> q;
q.push({stx,sty,0});
table[stx][sty]=0;
while(!q.empty())
{
node t=q.front();
q.pop();
table[t.x][t.y]=min(table[t.x][t.y],t.s);
for(int i=0;i<4;i++)
{
int tx=t.x+dx[i];
int ty=t.y+dy[i];
if(check(tx,ty) and table[tx][ty]>t.s+1)
{
q.push({tx,ty,table[tx][ty]=t.s+1});
}
}
}
}
int main()
{
cin>>n>>m>>d>>j;
int x,y;
memset(table,0x3f3f3f,sizeof table);
for(int i=1;i<=d;i++)
{
cin>>x>>y;
stx=x,sty=y;
bfs();
}
for(int i=1;i<=j;i++)
{
cin>>x>>y;
cout<<table[x][y];
puts("");
}
return 0;
}
```
by LG_kemeng @ 2023-12-24 15:11:23
还有一点更严重的我刚刚没想到。其实光memset应该不会这么严重的，主要是你完全没有考虑进行剪枝的操作。其实广搜也是可以有剪枝的。考虑这样一个问题：如果你搜索到一个点，时间不如之前已经搜索到这个点优秀，那是不是就根本没有把这个点加入搜索队列的必要了？应为由这个点出发搜索到的点很明显也不如之前的结果优秀，这样理论上可以少掉大半的常数。这可能才是你T的本质原因。
by LG_kemeng @ 2023-12-24 15:15:55