BFS Algorithm! （每AC一道题就要不停的问自已有没有继续优化的空间？）

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

using P = pair<int, int>;
static constexpr int dirs[] { 0, -1, 0, 1, 0 };

int n, m, k, d, x, y, amount;

int main(void) {
  cin >> n >> m >> k >> d;
  // obstacle(-1), shops(-1), customers(> 0) 
  vector<vector<int>> grid(n, vector<int>(n, 0));

  queue<P> q;
  while (m--) { // m 家店
    scanf("%d %d", &x, &y);
    grid[n - y][x - 1] = -1;

    q.emplace(x - 1, n - y);
  }
  for (int i = 0; i < k; ++i) { // k 位顾客
    scanf("%d %d %d", &x, &y, &amount);
    grid[n - y][x - 1] += amount;
  }
  while (d--) { // d个障碍物
    scanf("%d %d", &x, &y);
    grid[n - y][x - 1] = -1;
  }

  long ans = 0, steps = 0;
  while (not q.empty() && k) {
    size_t sz = q.size();
    while (sz--) {
      const auto [x, y] = q.front(); q.pop();
      for (int i = 0; i < 4; ++i) {
        int nx = x + dirs[i], ny = y + dirs[i + 1];
        if (nx < 0 || ny < 0 || nx == n || ny == n || grid[ny][nx] < 0)
           continue;
        if (grid[ny][nx] > 0) {
          ans += (steps + 1) * grid[ny][nx];
          --k;
        }
        q.emplace(nx, ny);
        grid[ny][nx] = -1; // mark as seen
      }
    }
    ++steps;
  }

  printf("%ld\n", ans);
}