Submission #1520917

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)
typedef vector<int> Edges;
Edges G[100005];
int color[100005];
int visited[100005];
/*
void dfs(int id, int vertex, int col, int max_dist, int dist){
    color[vertex] = col;
    visited[vertex] = id;
    REP(i, G[vertex].size()){
        int next = G[vertex][i];
        if(visited[next] != id && dist+1<=max_dist){
            dfs(id, next, col, max_dist, dist+1);
        }
    }
}
*/

int main(){
    int N, M;
    cin >> N >> M;
    REP(i, M){
        int a, b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int Q;
    cin >> Q;
    REP(i, N) color[i] = 0;
    REP(i, N) visited[i] = -1;
    REP(i, Q){
        int v, d, c;
        cin >> v >> d >> c;
        v--;

        //BFS
        queue<pii> que;
        que.push(make_pair(v, 0));
        while(!que.empty()){
            pii now = que.front();que.pop();
            int v_now = now.first;
            int dist_now = now.second;
            visited[v_now] = i;
            color[v_now] = c;
            REP(j, G[v_now].size()){
                int v_next = G[v_now][j];
                int dist_next = dist_now+1;
                if(visited[v_next] != i && dist_next <= d){
                    pii next = make_pair(v_next, dist_next);
                    que.push(next);
                }
            }
        }
    }
    REP(i, N) cout << color[i] << endl;
    return 0;
}

Submission Info

Judge Result