题解 P6145 【[USACO20FEB]Timeline G】
sukimo
2020-05-23 15:50:14
思路：拓扑排序+递推。把每一次挤奶的时间抽象为点，时间差关系抽象为有向边，就得到了一个DAG。对此DAG拓扑排序，每一次删点时尝试更新与该点相连的点的最早时间，由于要满足所有情况且最小，所以要用max比较。思路还是很经典的。
代码献上：
```
#include<bits/stdc++.h>
using namespace std;
const int MX=100005;int dp[MX],fir[MX],in_cnt[MX];queue<int>q;struct STR{int val,next,to;}edge[MX];
void add(int u,int v,int x,int cnt){
in_cnt[v]++;edge[cnt].val=x;edge[cnt].to=v;edge[cnt].next=fir[u];fir[u]=cnt;
}
int main(){
int n,m,k;scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%d",&dp[i]);
for(int i=1;i<=k;i++){
int u,v,x;scanf("%d%d%d",&u,&v,&x);add(u,v,x,i);
}
for(int i=1;i<=n;i++)if(!in_cnt[i])q.push(i);
while(!q.empty()){
int fr=q.front();
for(int i=fir[fr];i;i=edge[i].next){
if(!--in_cnt[edge[i].to])q.push(edge[i].to);dp[edge[i].to]=max(dp[edge[i].to],dp[fr]+edge[i].val);
}
q.pop();
}
for(int i=1;i<=n;i++)printf("%d\n",dp[i]);
return 0;
}
```