Submission #1242475

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mn=1e5+7;
ll ai[mn],bi[mn],ci[mn];
ll dp[mn][11];

int main(){
	ll n,m;cin>>n>>m;
	for(ll a=0;a<m;++a){cin>>ai[a]>>bi[a];--ai[a];--bi[a];}
	memset(dp,-1,sizeof(dp));
	ll q;cin>>q;
	for(ll a=0;a<q;++a){
		ll v,d;cin>>v>>d>>ci[a];
		--v;
		dp[v][d]=a;
	}
	for(ll a=10;a>=1;--a){
		for(ll b=0;b<n;++b)dp[b][a-1]=max(dp[b][a-1],dp[b][a]);
		for(ll b=0;b<m;++b){
			dp[ai[b]][a-1]=max(dp[ai[b]][a-1],dp[bi[b]][a]);
			dp[bi[b]][a-1]=max(dp[bi[b]][a-1],dp[ai[b]][a]);
		}
	}
	for(ll a=0;a<n;++a)cout<<(dp[a][0]>-1?ci[dp[a][0]]:0)<<endl;
	return 0;
}

Submission Info

Judge Result