很明显的拓扑
推一波:
https://www.luogu.com.cn/blog/Hehe-0/p2017-dizzy-cows-g
1 #include<bits/stdc++.h> 2 3 4 using namespace std; 5 const int mmm=1e6+1; 6 7 int n,m,c,cnt; 8 int to[mmm],nxt[mmm],ed[mmm]; 9 int tp[mmm],in[mmm],head[mmm]; 10 queue < int> q; 11 12 void add(int x,int y,int z) 13 { 14 cnt++; 15 to[cnt]=y; 16 ed[cnt]=z; 17 18 nxt[cnt]=head[x]; 19 head[x]=cnt; 20 21 return ; 22 } 23 24 void bfs() 25 { 26 for(int i=1;i<=n;i++) 27 if(!in[i])// 如果入度为0 28 q.push(i);//要所有的点都入队 29 30 31 while(!q.empty()) 32 { 33 int x=q.front(); 34 q.pop();//队头 35 for(int i=head[x];i;i=nxt[i]) 36 { 37 int y=to[i],z=ed[i]; 38 tp[y]=max(tp[y],tp[x]+z);//更新 39 in[y]--;//度- 40 if(!in[y])//让所有到0的点都入队 41 q.push(y); 42 } 43 } 44 45 46 return ; 47 } 48 49 int main() 50 { 51 ios::sync_with_stdio(false); 52 53 cin>>n>>m>>c; 54 for(int i=1;i<=n;i++) 55 cin>>tp[i]; 56 //此题要求拓扑序 57 for(int i=1;i<=c;i++) 58 { 59 int q,w,e; 60 cin>>q>>w>>e; 61 add(q,w,e); 62 in[w]++;//统计入度 63 } 64 65 bfs(); 66 67 for(int i=1;i<=n;i++) 68 cout<<tp[i]<<endl; 69 70 return 0; 71 }