Submission #1194675

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;

ll N,M;
vector<ll> vec[100100];
ll Q;
queue<ll> que;
ll ans[100100];

void bfs(ll v ,ll d, ll c){
  que.push(v);
  ans[v] = c;
  while(!que.empty() && d>0){
    ll l=que.size();
    d--;
    rep(i,l){
      ll tmp = que.front();
      que.pop();
      ll l2 = vec[tmp].size();
      rep(j,l2){
        ll pos = vec[tmp][j];
        ans[pos] = c;
        que.push(pos);
      }
    }
  }

  while(!que.empty()){
    que.pop();
  }
}
int main(){
  cin >> N >> M;
  rep(i,M){
    ll a,b;
    cin >> a >> b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  cin >> Q;
  rep(i,Q){
    ll v,d,c;
    cin >> v >> d >> c;
    bfs(v,d,c);
  }
  rep(i,N){
    cout << ans[i+1] << endl;
  }
}

Submission Info

Judge Result