Time limit : 2sec / Memory limit : 256MB

Score : 700 points

Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of N vertices numbered 1 through N, and M edges. Initially, all the vertices are painted in color 0. The i-th edge bidirectionally connects two vertices ai and bi. The length of every edge is 1.

Squid performed Q operations on this graph. In the i-th operation, he repaints all the vertices within a distance of di from vertex vi, in color ci.

Find the color of each vertex after the Q operations.

Constraints

• 1≤N,M,Q≤105
• 1≤ai,bi,vi≤N
• ai≠bi
• 0≤di≤10
• 1≤ci≤105
• di and ci are all integers.
• There are no self-loops or multiple edges in the given graph.

Partial Score

• 200 points will be awarded for passing the testset satisfying 1≤N,M,Q≤2,000.

---

Input

Input is given from Standard Input in the following format:

N Ma1 b1:aM bMQv1 d1 c1:vQ dQ cQ

Output

Print the answer in N lines. In the i-th line, print the color of vertex i after the Q operations.

---

Sample Input 1

Copy

7 71 21 31 44 55 65 72 326 1 11 2 2

Sample Output 1

Copy

2222210

Initially, each vertex is painted in color 0. In the first operation, vertices 5 and 6 are repainted in color 1. In the second operation, vertices 1, 2, 3, 4 and 5 are repainted in color 2.

****************************************************************************************************************************************************

题意：给你N个点，M条边（可能有点的没有边），有Q次染色操作，每次染第vi节点的di范围内的所有节点。节点的颜色可以被覆   盖。

解题思路：

1）暴力dfs

保存每一个顶点连同的顶点。

每一次输入v，d，c，搜索v节点的d范围内能够染色的点，每一次d-1;

2）dp

先贴上官方题解：https://agc012.contest.atcoder.jp/editorial;

**************************************************************************************************************************

简单翻译一下（虽然是看着jcvb dalao理解的）

dp[i][d]表示当前i节点d距离时的颜色，所以dp[i][0]为i节点的颜色，

所以就可以在dfs时判断如果当前节点dp[i][d]已经染了色，就可以不用染色了。

还有的就是：因为颜色是覆盖的，所以最后染的颜色就是结束的颜色。所以我们应该从后往前开始染色。

这样就可以保证，如果这节点d[i][0]染了色，就不会被覆盖了。

 

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long LL;const int maxn = 100000+10;int color[maxn][15];int v[maxn];int d[maxn];int c[maxn];vector 
            
              node[maxn];void paint(int v1, int d1, int c1){ if(d1==-1) return; if(color[v1][d1] ) return; color[v1][d1] = c1; for(int i =0;i
             
              > N >>M; for(int i=1;i<=M;i++){ int a, b; cin >> a >> b; node[a].push_back(b); node[b].push_back(a); } ///自己指向自己， 才能够自己跑到color[i][0] for(int i=1;i<=N;i++) node[i].push_back(i); int q; cin >> q; for(int i=1;i<=q;i++) cin >> v[i] >> d[i] >> c[i]; for(int i=q;i>=1;i--) paint(v[i], d[i], c[i]); for(int i=1;i<=N;i++) cout << color[i][0] << endl; return 0;}
             
            
           
          
         
        
       
      

可以用链式前向星来代替vector。