Submission #1586831

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
struct item {
	int v, d, c;
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, a, b;
	cin >> n >> m;
	vector<vector<int> > g(n + 10);
	vector<int> out(n + 10, 0);
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int q;
	cin >> q;
	int v, d, c;
	vector<item> vi;
	for (int i = 0; i < q; i++) {
		item it;
		cin >> it.v >> it.d >> it.c;
		vi.push_back(it);
	}
	queue<item> qi;
	vector<int> visited(n + 10, 0);
	for (int ii = q - 1; ii >= 0; ii--) {
		qi.push(vi[ii]);
		while (!qi.empty()) {
			item it = qi.front();
		//	cout << it.v << " " << it.d << " " << it.c << endl;
			qi.pop();
			if (!visited[it.v]) {
				visited[it.v] = ii + 1;
				out[it.v] = it.c;
			}
			if (it.d > 0) {
				for (int i = 0; i < g[it.v].size(); i++) {
					int x = g[it.v][i];
					item itx;
					itx.v = x;
					itx.d = it.d - 1;
					itx.c = 0;
					itx.c = it.c;
					if (!visited[x] || visited[x] != ii + 1) {
						/*cout << "children:" << endl;
						cout << itx.v << " " << itx.d << " " << itx.c << endl;*/
						qi.push(itx);
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << out[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result