LeLe422 @ 2024-03-30 15:42:42
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 310;
typedef pair<int,int> PII;
queue<PII> q;
int g[N][N],dist[N][N];
int m;
vector<PII> v(50010);
int T[1010];
int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
void fun(PII p, int weight){
int x=p.f, y=p.s;
g[x][y] = min(weight,g[x][y]);
for(int i=0; i<4; i++){
int a=x+dx[i], b=y+dy[i];
if(a<0 || b<0 || a>301 || b>301) continue;
g[a][b] = min(weight,g[a][b]);
}
}
int bfs(int x, int y){
q.push({x,y});
dist[x][y] = 0;
while(!q.empty()){
auto t =q.front();
q.pop();
for(int i=0; i<4; i++){
int a=t.f+dx[i], b=t.s+dy[i];
if(a<0 || b<0) continue;
if(dist[a][b]!=0) continue;
dist[a][b] = dist[t.f][t.s]+1;
if(dist[a][b] >= g[a][b]) continue;
q.push({a,b});
if(g[a][b] > 1e9) return dist[a][b];
}
}
return -1;
}
int main()
{
cin>>m;
int x,y,ti;
memset(g,0x3f,sizeof(g));
for(int i=0; i<m; i++){
scanf("%d%d%d",&x,&y,&ti);
v[i]={x,y};
T[i] = ti;
}
for(int i=0; i<m; i++){//预处理出流星矩阵
fun(v[i],T[i]);
}
cout<<bfs(0,0);
return 0;
}
by QuaternaryTree @ 2024-04-09 12:46:07
@LeLe422 N开320