asd1926 @ 2021-07-24 15:23:39
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e3 + 10;
int m;
int dist[1000][1000];
int time1[1000][1000];
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs () {
queue<PII> q;
memset (dist, 0x3f, sizeof dist);
q.push({0, 0});
dist[0][0] = 0;
if (time1[0][0] == 0) return -1;
st[0][0] = true;
while(q.size()) {
auto t = q.front(); q.pop();
int x = t.first, y = t.second;
if (time1[x][y] == 0x3f3f3f3f) return dist[x][y];
for (int i = 0; i < 4; i ++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx > 300 || ny < 0 || ny > 300) continue;
if (st[nx][ny]) continue;
int d = dist[x][y] + 1;
if (d >= time1[nx][ny]) continue;
st[nx][ny] = true;
dist[nx][ny] = d;
q.push({nx, ny});
}
}
return -1;
}
int main () {
cin >> m;
memset (time1, 0x3f, sizeof time1);
for (int i = 0; i < m; i ++) {
int x, y, t;
cin >> x >> y >> t;
time1[x][y] = t;
if (x >= 1) time1[x - 1][y] = t;
if (x < 300) time1[x + 1][y] = t;
if (y >= 1) time1[x][y - 1] =t;
if (y < 300) time1[x][y + 1] = t;
}
cout << bfs() << endl;
return 0;
}
by asd1926 @ 2021-07-24 15:36:58
已解决