自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:17:53，当前版本为作者最后更新于2020-03-01 12:51:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于每个三元组 $(a,b,x)$，从 $a$ 向 $b$ 连一条长度为 $x$ 的边。同时新建一个超级源点 $0$，从 $0$ 向 $i$ 连长度为 $S_i$ 的边。

容易发现这张图是一个 DAG。

直接拓扑排序递推计算即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct edge
{
 int v,w,next;
}e[100005];
int s[100005],t[100005],head[100005],cnt;
queue<int> q;
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
int main()
{
 freopen("timeline.in","r",stdin);
 freopen("timeline.out","w",stdout);
 ios::sync_with_stdio(false);
 int n,m,c;
 cin>>n>>m>>c;
 for(int i=1;i<=n;i++)
  cin>>s[i];
 for(int i=1;i<=c;i++)
 {
  int u,v,w;
  cin>>u>>v>>w;
  addedge(u,v,w);
  t[v]++;
 }
 for(int i=1;i<=n;i++)
  if(!t[i])q.push(i);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  for(int i=head[u];i;i=e[i].next)
  {
   int v=e[i].v,w=e[i].w;
   s[v]=max(s[v],s[u]+w);
   t[v]--;
   if(!t[v])q.push(v);
  }
 }
 for(int i=1;i<=n;i++)
  cout<<s[i]<<endl;
 return 0;
}