比赛 2025暑期集训第5场图论专场 评测结果 AAAAAAAAAA
题目名称 Timeline 最终得分 100
用户昵称 小福鑫 运行时间 1.411 s
代码语言 C++ 内存使用 5.76 MiB
提交时间 2025-07-09 10:38:04
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,c,a,b,x,cnt,s[200001],t[200001],h[200001],to[200001],cost[200001],nxt[200001];
queue<int> q;
void add(int a,int b,int c){
	to[++cnt]=b;
	cost[cnt]=c;
	nxt[cnt]=h[a];
	h[a]=cnt;
}
signed main(){
	freopen("usaco_Feb_timeline.in","r",stdin);
	freopen("usaco_Feb_timeline.out","w",stdout);
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=c;i++){
		cin>>a>>b>>x;
		add(a,b,x);
		t[b]++;
	}
	for(int i=1;i<=n;i++){
		if(!t[i]){
			q.push(i);
		}
	}
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=nxt[i]){
			s[to[i]]=max(s[to[i]],s[u]+cost[i]);
			t[to[i]]--;
			if(!t[to[i]]){
				q.push(to[i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<s[i]<<endl;
	}
}