记录编号	603157	评测结果	AAAAAAAAAA
题目名称	3365.[USACO20 Feb Gold]Timeline	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.743 s
提交时间	2025-07-09 14:49:48	内存使用	7.49 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e6+100;

ll n,m,c;
ll s[N];
ll head[N],nxt[N],to[N],fy[N],cnt;
ll dis[N],tot[N];
bool check[N];
queue<ll> q;

void add(ll u,ll v,ll w){
	to[++cnt]=v;
	fy[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void spfa(ll o){
	dis[o]=0;
	check[o]=1;
	tot[o]++;
	q.push(o);
	while(!q.empty()){
		ll u=q.front();q.pop();
		check[u]=0;
		for (int i=head[u];i;i=nxt[i]){
			ll v=to[i],w=fy[i];
			if (dis[v]<dis[u]+w){
				dis[v]=dis[u]+w;
				tot[v]++;
				if (tot[v]>=n+1) return;
				if (!check[v]) {
					q.push(v);
					check[v] = 1;
				}
			}
		}
	}
	return;
}

int main(){
	freopen("usaco_Feb_timeline.in","r",stdin);
	freopen("usaco_Feb_timeline.out","w",stdout);
	scanf("%lld %lld %lld",&n,&m,&c);
	for (int i=1;i<=n;i++) dis[i]=-0x3f3f3f3f;
	for (int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
		add(0,i,s[i]);
	}
	for (int i=1;i<=c;i++){
		ll u,v,w;
		scanf("%lld %lld %lld",&u,&v,&w);
		add(u,v,w);
	}
	spfa(0);
	for (int i=1;i<=n;i++){
		printf("%lld\n",dis[i]);
	}
	return 0;
}