Submission #1369499

---

Source Code Expand

/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 1e5 + 10, MAXD = 11;

int n, m, q;
int c[MAXN], v, d;
vector <int> g[MAXN];
int dp[MAXN][MAXD];

int main(){
    #ifndef SAKO
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    #endif // SAKO
    ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i){
		cin >> v >> d;
		g[v].pb(d);
		g[d].pb(v);
	}
	cin >> q;
	for (int i = 1; i <= q; ++i){
		cin >> v >> d >> c[i];
		dp[v][d] = i;
	}
	for (int i = 9; i >= 0; --i){
		for (int j = 1; j <= n; ++j){
			dp[j][i] = max(dp[j][i], dp[j][i + 1]);
			for (auto to : g[j]){
				dp[j][i]=max(dp[j][i], dp[to][i + 1]);
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		cout << c[dp[i][0]] << "\n";

    return 0;
}

Submission Info

Judge Result