作者：相依相随
链接：https://www.nowcoder.com/discuss/719729?type=post&order=time&pos=&page=3&ncTraceId=&channel=-1&source_id=search_post_nctrack
来源：牛客网

package nowcoder;
 
import java.io.BufferedInputStream;
import java.util.*;
 
public class Main49 {
    public static void main(String[] args) {
        new Solve49().solve();
    }
}
 
class Solve49{
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int n=s.nextInt();
        int[] times=new int[n];
        s.nextLine();
        List<List<Integer>> graph=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            String str=s.nextLine();
            String[] strs=str.split(",");
            for (int j = 0; j <strs.length-1 ; j++) {
                int a=Integer.parseInt(strs[j]);
                graph.get(a).add(i);
            }
            String[] curr=strs[strs.length-1].split(" ");
            if (!curr[0].equals("-1")){
                int a=Integer.parseInt(curr[0]);
                graph.get(a).add(i);
            }
            int t=Integer.parseInt(curr[1]);
            times[i]=t;
        }
        System.out.println(getAns(times,graph,n));
    }
    private int getAns(int[] times,List<List<Integer>> graph,int n){
        int[] in=new int[n];
        for(List<Integer> list:graph){
            for(int i:list)in[i]++;
        }
        Queue<Integer> queue=new LinkedList<>();
        int[] dp=new int[n];
        Arrays.fill(dp,0);
        int cnt=0;
        for (int i = 0; i < n; i++) {
            if (in[i]==0){
                dp[i]=times[i];
                queue.add(i);
            }
        }
        while (!queue.isEmpty()){
            int curr=queue.poll();
            cnt++;
            for(int i:graph.get(curr)){
                in[i]--;
                dp[i]=Math.max(dp[i],dp[curr]+times[i]);
                if (in[i]==0)queue.add(i);
            }
        }
        if (cnt!=n)return -1;
        int ans=0;
        for (int i = 0; i <dp.length ; i++) {
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
 
}