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.

Sample Input 1

7 7

1 2

1 3

1 4

4 5

5 6

5 7

2 3

2

6 1 1

1 2 2

Sample Output 1

2

2

2

2

2

1

0

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.

Sample Input 2

14 10

1 4

5 7

7 11

4 10

14 7

14 3

6 14

8 11

5 13

8 3

8

8 6 2

9 7 85

6 9 3

6 7 5

10 3 1

12 9 4

9 6 6

8 2 3

Sample Output 2

1

0

3

1

5

5

3

3

6

1

3

4

5

3

The given graph may not be connected.

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

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

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

我们从3处理，距离是2

3的处理范围2

2的处理范围1

1的处理范围0

4的处理范围1

5的处理范围0

就是说1,5已经到染色边界了

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

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 vector<int>q[];

 int color[];

 int flag[];

 int n,m;

 int v[],d[],c[];

 void dfs(int x,int cnt,int c)

 {

    if(!color[x])

    {

        color[x]=c;

    }

    if(flag[x]>=cnt)

    {

        return;

    }

    if(cnt==)

    {

        return;

    }

    flag[x]=cnt;

    for(int i=;i<q[x].size();i++)

    {

        dfs(q[x][i],cnt-,c);

    }

 }

 int main()

 {

     std::ios::sync_with_stdio(false);

     cin>>n>>m;

     for(int i=;i<=m;i++)

     {

         int x,y;

         cin>>x>>y;

         q[x].push_back(y);

         q[y].push_back(x);

     }

     int q;

     cin>>q;

     for(int i=;i<=q;i++)

     {

        cin>>v[i]>>d[i]>>c[i];

     }

     for(int i=q;i>=;i--)

     {

         dfs(v[i],d[i],c[i]);

     }

     for(int i=;i<=n;i++)

     {

         cout<<color[i]<<endl;

     }

     return ;

 }