【DP】AGC012B Splatter Painting

分析：

很简单的DP水题。

定义$DP(i,j)=(x,y)$表示在i号点，将其周围j个格子全部转化为颜色y，其优先级为x的最优先操作。

只不过有点不同的是，这个DP的初始状态是一来就直接给出的。

对于一个操作(v,c,d)，其优先级为i（第i次操作），将DP(v,d)=max(DP(v,d),(i,c));

转移式就非常简单了：$DP(i,j)=max(DP(i,j),DP(i,j+1),DP(u,j+1))$
u是与i相邻的节点。

每个点最终的颜色就是$(DP(i,0).second)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
pair<int,int> dp[MAXN][12];
int n,m,q;
vector<int> a[MAXN];
int main(){SF("%d%d",&n,&m);int u,v;for(int i=1;i<=m;i++){SF("%d%d",&u,&v);a[u].push_back(v);a[v].push_back(u);}SF("%d",&q);int d,c;for(int i=1;i<=q;i++){SF("%d%d%d",&v,&d,&c);dp[v][d]=make_pair(i,c);}for(int k=9;k>=0;k--)for(int i=1;i<=n;i++){dp[i][k]=max(dp[i][k],dp[i][k+1]);for(int j=0;j<int(a[i].size());j++){v=a[i][j];dp[i][k]=max(dp[i][k],dp[v][k+1]);}}for(int i=1;i<=n;i++)PF("%d\n",dp[i][0].second);
}