Submission #1195287

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int N, M, Q;
vector< vector<int> > graph;
vector< vector<int> > dist;

void bfs(int s) {
  dist[s].resize(N, inf);
  queue<int> que;
  que.push(s);
  dist[s][s] = 0;
  while(que.size()) {
    int v = que.front(); que.pop();
    for(int to : graph[v]) {
      if(dist[s][to] == inf) {
	dist[s][to] = dist[s][v] + 1;
	que.push(to);
      }
    }
  }
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> M;
  graph.resize(N);
  rep(i, M) {
    int a, b;
    cin >> a >> b; --a, --b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  dist.resize(N);
  rep(i, N) bfs(i);
  cin >> Q;
  vector<int> color(N, 0);
  rep(i, Q) {
    int v, d, c;
    cin >> v >> d >> c; --v;
    rep(j, N) {
      if(dist[v][j] <= d) color[j] = c;
    }
  }
  rep(i, N) cout << color[i] << endl;

  return 0;
}

Submission Info

Judge Result