Submission #1370416

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#define int long long
using namespace std;

int n,m,q,v[100000],d[100000],c[100000];
int color[100000] = {},maxd[100000] = {};
vector<int> G[100000];

signed main(){
	cin >> n >> m;
	for(int i = 0;i < n;i++) maxd[i] = -1;
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	cin >> q;
	for(int i = 0;i < q;i++) {
		cin >> v[q - i - 1] >> d[q - i - 1] >> c[q - i - 1];
		v[q - i - 1]--;
	}
	queue<int> que;
	for(int i = 0;i < q;i++){
		if(maxd[v[i]] < d[i]){
			que.push(v[i]);
			for(int j = d[i];j >= 0;j--){
				int siz = que.size();
				for(int k = 0;k < siz;k++){
					int nowv = que.front();que.pop();
					maxd[nowv] = j;
					if(!color[nowv]) color[nowv] = c[i];
					for(int l = 0;l < G[nowv].size();l++){
						int to = G[nowv][l];
						if(maxd[to] < j - 1) que.push(to);
					}
				}
			}
		}
	}
	for(int i = 0;i < n;i++) cout << color[i] << endl;
	return 0;
}

Submission Info

Judge Result