Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.3 kB
1
Indexable
Never
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, m;
    cin >> n >> m;
    queue<ll> q;
    vector<vector<ll>> a(n);
    for (int i = 0; i < m; ++i) {
        ll from, to;
        cin >> from >> to;
        from--;
        to--;
        a[from].push_back(to);
        a[to].push_back(from);
    }
    ll quest;
    cin >> quest;
    vector<vector<ll>> quest_list(quest, vector<ll>(3));
    for (int i = 0; i < quest; ++i) {
        cin >> quest_list[i][0] >> quest_list[i][1] >> quest_list[i][2];
        quest_list[i][0]--;
    }
    vector<ll> colors(n);
    for (int i = 0; i < quest; ++i) {
        ll v = quest_list[i][0], d = quest_list[i][1], c = quest_list[i][2];
        queue<ll> q;
        vector<ll> used(n, -1);
        q.push(v);
        colors[v] = c;
        used[v] = 0;
        while (!q.empty()) {
            ll ver = q.front();
            q.pop();
            for (auto x : a[ver]) {
                if (used[x] == -1 && used[ver] < d) {
                    used[x] = used[ver] + 1;
                    colors[x] = c;
                    q.push(x);
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << colors[i] << "\n";
    }
}