比赛 |
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;
}
}