拓扑模板
作者:
一条代码
,
2022-11-25 09:44:23
,
所有人可见
,
阅读 165
#include<bits/stdc++.h>
using namespace std;
int n;
struct text{
int len,num,indegree,vis;
vector<int> a;
}t[10010];
//序号,工作时间,前置工作
//最短时间
int ans = 0;
void dfs(int s,int time)
{ int i;
ans = max(ans,time);
t[s].vis = 1;
for(i = 0 ; i < t[s].a.size() ; i ++){
if(!t[t[s].a[i]].vis){
t[t[s].a[i]].indegree--;
}
}
for(i = 0 ; i < t[s].a.size() ; i ++){
if(!t[t[s].a[i]].vis){
dfs(t[t[s].a[i]].num,t[t[s].a[i]].len+time);
}
}
for(i = 0 ; i < t[s].a.size() ; i ++){
if(!t[t[s].a[i]].vis){
t[t[s].a[i]].indegree++;
}
}
t[s].vis=0;
}
int main(){
scanf("%d",&n);
for(int i = 1 ; i <= n ; i ++){
t[i].indegree = 0;
int num,len,cnt=0,tmp;
scanf("%d %d",&t[i].num,&t[i].len);
while(1){
scanf("%d",&tmp);
if(tmp==0)break;
t[tmp].a.push_back(i);
t[i].indegree++;
}
}
for(int i = 1; i <= n ; i ++){
if(!t[i].indegree)
{
dfs(t[i].num,t[i].len);
}
}
printf("%d",ans);
}