Submission #1516665

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using P = pair<int, int>;

vector<vector<int>> G;
vector<int> color;

void bfs(int s, int d, int c) {
  int N = G.size();
  vector<bool> used(N, false);
  queue<P> que;
  que.push({s, d});
  used[s] = true;
  if (color[s] == 0) color[s] = c;
  while (!que.empty()) {
    P p = que.front(); que.pop();
    int u = p.first, l = p.second;
    if (l == 0) continue;
    for (auto&& v : G[u]) {
      if (used[v]) continue;
      used[v] = true;
      if (color[v] == 0) color[v] = c;
      que.push({v, l - 1});
    }
  }
}

main() {
  int N, M; cin >> N >> M;
  G.resize(N);
  color.assign(N, 0);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int Q; cin >> Q;
  vector<int> v(Q), d(Q), c(Q);
  for (int i = 0; i < Q; i++) {
    cin >> v[i] >> d[i] >> c[i];
    v[i]--;
  }
  for (int i = 0; i < Q; i++) {
    int pos = Q - i - 1;
    bfs(v[pos], d[pos], c[pos]);
  }
  for (int i = 0; i < N; i++) cout << color[i] << endl;
}

Submission Info

Judge Result