拓扑排序做法求助
#include<bits/stdc++.h>
using namespace std;
#define LF putchar('\n')
#define SP putchar(' ')
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define repp(i,a,b) for(register int i=(a);i>=(b);i--)
#define pill pair<int,int>
#define mem(t, v) memset((t),v,sizeof(t))
#define fir first
#define sec second
#define mk make_pair
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define lc root<<1
#define rc root<<1|1
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
void read(T &x) {x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;}
template<typename T, typename... Args>
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x=arg;if(x<0) {putchar('-');x=-x;}if(x>9) {write(x/10);}putchar(x%10+'0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args)!=0) {putchar(' ');write(args ...);}}
const ll mod=10007,N=1e4+10,M=1e6+10;
int head[M],tot,n,cost[N],dist[N],indx[N],maxx;
queue<int> q,cl;
struct node{
int u,v,w,nex;
}edge[M];
void add(int a,int b,int w){
edge[++tot]=(node){a,b,w,head[a]};
head[a]=tot;
}
void BFS(int start){
q=cl;
q.push(start);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];~i;i=edge[i].nex){
int v=edge[i].v;
indx[v]--;
dist[v]=max(dist[v],dist[u]+edge[i].w);
if(indx[v]==0){
q.push(v);
}
}
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
memset(head,-1,sizeof head);
read(n);
rep(i,1,n){
int u,t,v;
read(v,t);
cost[v]=t;
while(1){
read(u);
if(u==0)break;
indx[v]++;
add(u,v,cost[u]);
}
}
rep(i,1,n){
if(indx[i]==0 and dist[i]==0)BFS(i);
}
rep(i,1,n){
maxx=max(maxx,dist[n]+cost[n]);
}
write(maxx);
// fclose(stdin);
// fclose(stdout);
return 0;
}