Family Trivia

One   Link to original question

Chores - POJ 1949 - Virtual Judgehttps://vjudge.net/problem/POJ-1949

Two   Input and output

1  Input

The first 1 Line contains an integer  N. The first 2 ~ N+1  Line describes each household chore , The first 2 Line contains housework 1; The first 3 Line contains housework 2, And so on . Each line contains the time to complete the housework 、 Number of prerequisites  Pi  and  Pi  A prerequisite .

2  Output

Single line output the minimum time required to complete all housework .

3、 ... and   Input and output samples

1  Input

7

5 0

1 1 1

3 1 2

6 1 1

1 2 2 4

8 2 2 4

4 3 3 5 6

2  Output

23

Four   Analysis and design

1  Topology

 2  analysis

The housework 1 In time 0 Start , In time 5 end ;

The housework 2 In time 0 Start , In time 6 end ;

The housework 3 In time 0 Start , In time 9 end ;

The housework 4 In time 0 Start , In time 11 end ;

The housework 5 In time 0 Start , In time 12 end ;

The housework 6 In time 0 Start , In time 19 end ;

The housework 7 In time 0 Start , In time 23 end ;

The key to this problem lies in , The housework  k  Only housework 1~k-1  As a prerequisite . in other words , Enter the first  K  When doing housework , Its prerequisites have determined when it will end . Therefore, in the input process, you can directly find the longest distance . If there are no preconditions , Then it can't be calculated in this way .

5、 ... and Code

package graph.poj1949;

import java.util.Scanner;

public class POJ1949 {
    static final int maxn = 10010;
    static int d[] = new int[maxn];
    static int n;

    public static void main(String[] args) {
        int ans = 0, w, num, y;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            w = scanner.nextInt();
            num = scanner.nextInt();
            d[i] = w;
            for (int j = 1; j <= num; j++) {
                y = scanner.nextInt();
                d[i] = Math.max(d[i], d[y] + w);
            }
            ans = Math.max(ans, d[i]);
        }
        System.out.println(ans);
    }
}

6、 ... and test

Green is the input , White is the output