tangguochao @ 2022-01-26 18:52:51
#include "bits/stdc++.h"
using namespace std;
const int N = 500;
int n = 0;
int v[N][N];
typedef struct {
int x, y, tt;
} PII;
queue<PII>q;
int dx[]={-1,1,0, 0};
int dy[]={0, 0, 1, -1 };
const int inf = 0x7fffffff;
void bfs()
{
while (!q.empty())
{
int x = q.front().x, y = q.front().y, t = q.front().tt;
if(v[x][y] == inf)
{
cout << t;
return;
}
q.pop();
for(int i=0; i<=3; i++)
{
int ux = x + dx[i], uy = y + dy[i];
if(ux>=0 && uy>=0)
if (t + 1 < v[ux][uy])
q.push({ux, uy, t + 1});
}
}
cout << -1;
}
int main()
{
cin.tie(0);
int m; cin >> m;
fill(v[0], v[0] + N*N, inf);
while (m--)
{
int x, y, t; cin >> x >> y >> t;
v[x][y] = min(v[x][y], t);
for(int i=0; i<=3; i++)
{
int ux = x + dx[i], uy = y + dy[i];
if (ux >= 0 && uy >= 0)
v[ux][uy] = min(v[ux][uy], t);
}
}
q.push({0, 0, 0});
bfs();
return 0;
}