peppaking8 @ 2019-07-25 21:03:31
救救孩子。。。最后几个点TLE和MLE,请求大佬优化。。。
#include<bits/stdc++.h>
using namespace std;
struct Node{
int x,y;
int step;
bool operator < (const Node &x)const{
return step>x.step;
}
}t,nt;
int m;
int meet[305][305];
bool vis[305][305];
int pos[5][2]={0,0,0,1,0,-1,1,0,-1,0};
priority_queue<Node>q;
void bfs(){
t.x=0,t.y=0,t.step=0;
q.push(t);
while(!q.empty()){
t=q.top();
q.pop();
if(meet[t.x][t.y]==0x3f3f3f3f){
printf("%d",t.step);
return ;
}
for(int i=1;i<5;i++){
nt.x=t.x+pos[i][0];
nt.y=t.y+pos[i][1];
nt.step=t.step+1;
if(nt.x<0) continue;
if(nt.y<0) continue;
if(!vis[nt.x][nt.y]&&nt.step<meet[nt.x][nt.y]){
q.push(nt);
}
}
}
printf("-1");
}
int main(){
scanf("%d",&m);
for(int i=0;i<=300;i++){
for(int j=0;j<=300;j++){
meet[i][j]=0x3f3f3f3f;
}
}
for(int i=1;i<=m;i++){
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
for(int i=0;i<5;i++){
int r1=x+pos[i][0];
int r2=y+pos[i][1];
if(r1<0||r2<0) continue;
if(meet[r1][r2]>t) meet[r1][r2]=t;
}
}
bfs();
return 0;
}
by wuyutong111 @ 2019-07-25 21:05:25
蒟蒻路过……
by peppaking8 @ 2019-07-25 21:12:20
简单的BFS啊,就是T了。。。求助!
by tythen @ 2019-07-25 21:15:15
简单的BFS不需要用priority_queue的,又不是最短路什么的(゜ロ゜)
by peppaking8 @ 2019-07-25 21:16:22
@tythen 就是把答案排个序嘛。。。
by peppaking8 @ 2019-07-25 21:16:44
是改成queue吗?
by tythen @ 2019-07-25 21:18:16
@用户未知 是的哦,因为BFS是按层搜索的,答案每一层是不需要排序的
by peppaking8 @ 2019-07-25 21:18:56
@tythen 提交了,MLE是没了,但是一堆T。。。
by tythen @ 2019-07-25 21:21:03
@用户未知 那么bfs写错了吧,你防止重复搜索的vis好像没用上吧
by peppaking8 @ 2019-07-25 21:22:11
知道了,脑抽了。。。大佬orz
by dingcx @ 2020-01-28 13:59:45
orz AKIOI的大佬wxb %%%