P6145 玄关求调

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200009;
int n,m,c;
int sum,ans[MAXN],in[MAXN];
int s[MAXN],head[MAXN];
struct edge{
	int next;
	int to;
	int h;
}d[MAXN];
void add(int u,int v,int w){
	d[++sum].next=head[u];
	d[sum].to=v;
	d[sum].h=w;
	head[u]=sum;
}
queue<int> q;
int main(){
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=c;i++){
		int a,b,x;
		cin>>a>>b>>x;
		in[b]++;
		add(a,b,x);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	while(q.empty()){
		int k=q.front();
		q.pop();
		for(int i=head[k];i;i=d[i].next){
			int s=d[i].to;
			ans[s]=max(ans[s],ans[k]+d[i].h);
			in[s]--;
			if(in[s]==0){
				q.push(s);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}