P1113 杂务(拓扑排序）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
vector<int>v[maxn];
int cost[maxn];
int indge[maxn];
int dp[maxn];
int n,a,b,c,d;
queue<int>q;
void topsort()
{
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++){
        if(indge[i]==0){
            q.push(i);
            dp[i]=cost[i];
        }
    }
    while(!q.empty()){
        int k=q.front();
        q.pop();
        for(int i=0;i<v[k].size();i++){
            if(--indge[v[k][i]]==0)q.push(v[k][i]);
            dp[v[k][i]]=max(dp[k]+cost[v[k][i]],dp[v[k][i]]);
        }
    }
}
int main()
{
    cin>>n;
    fill(dp,dp+maxn,0);
    fill(cost,cost+maxn,0);
    fill(indge,indge+maxn,0);
    for(int o=1;o<=n;o++){
        cin>>a>>b;
        cost[a]=b;
        cin>>c;
        while(c!=0){
            v[c].push_back(a);
            cin>>c;
            indge[a]++;
        }
    }
    topsort();int maxx=-1;
    for(int i=1;i<=n;i++){
         maxx=max(dp[i],maxx);
    }
    cout<<maxx<<endl;
    return 0;
}