这题有三个解法（其中一个不太会。。。）：

算法一：贪心，因为已经有顺序了。。就是求一下做前n个任务需要的最小时间，然后就好了。。

include

using namespace std;

int n,k,f[10010],ans,t;

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++){

    scanf("%d%d",&k,&t);

    while(scanf("%d",&k)&&k) f[i]=max(f[i],f[k]);

    f[i]+=t;

    ans=max(ans,f[i]);

}

printf("%d",ans);

return 0;

}

算法二：最短路算法，换一个松弛方向，就可以了。。

因为这题是保证无环的，所以可以直接建图后跑一遍最长路就行了，

为了优化一下复杂度，先建一个点0，就可以让从第0个任务开始求了：

include

using namespace std;

int n,len[10010],q[10010],d[10010];

bool ro[10010],vis[10010];

vector g[10010];

int spfa(int s){

int l=0,r=1;

q[l]=s;

vis[s]=true;

memset(d,0,sizeof d);

while(l!=r){

    int u=q[l++];l%=10007;vis[u]=false;

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];

        if(d[v]<d[u]+len[v]){

            d[v]=d[u]+len[v];

            if(!vis[v]){

                q[r++]=v;

                r%=10007;

                vis[v]=true;

            }

        }

    }

}

int ans=0;

for(int i=1;i<=n;i++)if(d[i]>ans)ans=d[i];

return ans;

}

int main(){

scanf("%d",&n);

for(int i=1,id,x;i<=n;i++){

    scanf("%d%d",&id,len+i);

    while(1){

        scanf("%d",&x);

        if(x==0) break;

        g[x].push_back(id);

        ro[id]=true;

    }
}
for(int i=1;i<=n;i++) if(!ro[i]) g[0].push_back(i);

printf("%d", spfa(0));

return 0;

}

算法三：拓扑排序（标算）：

我不会。。。