0LCH0 @ 2024-01-19 08:37:22
#include<bits/stdc++.h>
using namespace std;
int dis[501][501],dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0},g[501][501],ux,uy,vx,vy;
int n,m;
bool check(int x,int y){
if(x<1||y<1||x>400||dis[x][y]!=-1)
return 0;
}
int bfs(int x,int y)
{
queue<int>qx,qy;
qx.push(x);
qy.push(y);
dis[x][y]=0;
int rx,ry;
while(!qx.empty()){
rx = qx.front();
qx.pop();
ry = qy.front();
qy.pop();
if(g[ux][uy]=0x3f3f3f3f)
return dis[ux][uy];
for(int i=1,tx,ty;i<=4;i++){
vx = ux +dx[i];
vy = uy +dy[i];
if(check(vx,vy)&&g[vx][vy]>dis[ux][uy]+1){
dis[vx][vy]=dis[ux][uy]+1;
qx.push(vx);
qy.push(vy);
}
}
}
return -1;
}
int main()
{
cin>>m;
memset(dis,-1,sizeof(dis));
memset(g,0x3f,sizeof(g));
for(int i=1,u,v,t;i<=m;i++){
cin>>u>>v>>t;
u=u+1;
v=v+1;
for(int j=0;i<5;j++)
g[u+dx[j]][v+dy[j]]=min(g[u+dx[j]][v+dy[j]],t);
}
cout<<bfs(1,1);
return 0;
}