Problem

Time limit : 2sec / Memory limit : 256MB

door♂

题意简述：可以参考图，问你最后的染色情况

Solution

因为后面的染色会覆盖前面的，我们就倒过来处理，另外保存每个点的范围

比如$1-2-3-4-5-6$，

我们从$3$处理，距离是$2$
$3$的处理范围$2$
$2$的处理范围$1$
$1$的处理范围$0$
$4$的处理范围$1$
$5$的处理范围$0$

于是$1,5$已经到染色边界了

那么每次染色我们都比较上一次这个点的处理范围，比这一次的大，说明一定会被上一次的覆盖，没必要遍历下去了，或者处理没有染色的部分

Code:

Click to show/hide the code

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100000 + 10;
typedef long long ll;
vector<int> q[MAXN];
int color[MAXN];
int flag[MAXN];
int n, m, k;
int v[MAXN], d[MAXN], c[MAXN];
void dfs(int x, int cnt, int c)
{
	if (!color[x])
		color[x] = c;
	if (flag[x] >= cnt)
		return;
	if (cnt == 0)
		return;
	flag[x] = cnt;
	for (int i = 0; i < q[x].size(); i++)
		dfs(q[x][i], cnt - 1, c);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		q[x].push_back(y);
		q[y].push_back(x);
	}
	
	cin >> k;
	for (register int i = 1; i <= k; i++)
		cin >> v[i] >> d[i] >> c[i];
	for (register int i = k; i >= 1; i--)
		dfs(v[i], d[i], c[i]);
	for (register int i = 1; i <= n; i++)
		cout << color[i] << "\n";
	return 0;
}