AGC012B Splatter Painting

トランスファゲート
題意:n個のノードの簡単な無方向図(重辺、自環がない)をあげて、m本の辺を含みます.現在q回の操作があります.初期の時点ですべてのポイントの色は0です.各動作の説明は、ノードv[i]を選択し、このノードとの距離がd[i]以下の点をすべて色c[i]に染める.今、このq回の操作を完了した後、各点の最終色は何ですか.
问题解:この问题dはとても小さくて(≤10)、暴力を振るうことができます.しかし、直接暴力はT(例:菊花図)になる可能性がある.操作を逆さに考えると、このノードとの距離がd[i]以下で染色されていない点をすべて色c[i]に染めることになる.maxd[u]がu点で操作された最大距離であることを維持すると、現在の距離がmaxd[u]以下である場合、今回の操作は後の操作で相殺され、無視できることを示します.では,1点あたり最大10回しかアクセスされないため,時間的複雑度はO(nd)O(nd)O(nd)である.ここでは起点だけでなく,アクセスした点も残距離とmaxdの関係を判断することに注意する.
コード:

#include
#include
#define INF 0x3f3f3f3f
#define maxn 100005
int n,m,q,s[maxn],d[maxn],x[maxn],maxd[maxn],c[maxn],que[maxn],fr,bk;
struct node { int v; node *nxt; } edge[maxn*2],*head[maxn],*ncnt;
void addedge(int u,int v)
{
	ncnt++;
	ncnt->v=v,ncnt->nxt=head[u];
	head[u]=ncnt;
}
void dfs(int u,int d,int x)
{
	if(maxd[u]>=d) return;
	if(!c[u]) c[u]=x;
	if(!d) return;
	maxd[u]=d;
	for(node *p=head[u];p;p=p->nxt) dfs(p->v,d-1,x);
}
int main()
{
	scanf("%d%d",&n,&m);
	ncnt=&edge[0];
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v); addedge(v,u);
	}
	memset(maxd,-1,sizeof(maxd));
	scanf("%d",&q);
	for(int i=1;i<=q;i++) scanf("%d%d%d",&s[i],&d[i],&x[i]);
	for(int i=q;i;i--) dfs(s[i],d[i],x[i]); 
	for(int i=1;i<=n;i++) printf("%d
",c[i]);
}