[白俊]#2056作業

質問する

実行するタスクはN個あります(3≦N≦10000).ジョブあたりの所要時間(1≦時間≦100)は整数です.
一部の任務の間には先行関係があり、一部の任務は先に完成しなければ完成できない.これらのジョブ番号は非常にきれいで、K番ジョブに対しては、先決関係(すなわち、K番ジョブを開始する前に先に完了しなければならない)にあるジョブ番号がいずれも1以上(K-1)以下である.これらのジョブには、前置関係のないジョブが1つ以上存在する必要があります.(1番の仕事はいつもそうです)
すべてのタスクを完了するのに要する最短時間を見つけます.もちろん、先行関係のない仕事は同時に行うことができます.

入力

1行目はNです.
2行目からN+1行目までN行あります.2行目は1番目のタスク、3行目は2番目のタスク、...、N+1行はそれぞれN回の動作を表す.各行の先頭には、まずタスクに要する時間が与えられ、その後、タスクに対して前置関係のタスク個数(0≦個数≦100)が与えられる.次に、前提関係にあるジョブの番号を指定します.

しゅつりょく

最初の行は、すべてのタスクを完了する最小時間を出力します.

入力例1

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

サンプル出力1

23

に答える

この問題は位相ソートアルゴリズムで解決できる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static int ans = 0;
    static int N;
    static int[] time;
    static int[] cnt;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        time = new int[N+1];
        cnt = new int[N+1];
        list = new ArrayList[N+1];
        for(int i=1; i<=N; i++)
            list[i] = new ArrayList<>();

        for(int i=1; i<=N; i++) {
            String[] input = br.readLine().split(" ");
            int t = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            time[i] = t;

            for(int j=0; j<m; j++) {
                list[Integer.parseInt(input[j+2])].add(i);
                cnt[i]++;       //선행 일 갯수 체크
            }
        }

        sol();

        System.out.println(ans);
    }

    public static void sol() {
        PriorityQueue<Work> pq = new PriorityQueue<>();   //완료 시간순 정렬을 위한 우선순위 큐

        for(int i=1; i<=N; i++) {     //선행 일이 없는 경우
            if(cnt[i]==0) {
                pq.add(new Work(time[i], i));
            }
        }

        while(!pq.isEmpty()) {
            Work w = pq.poll();

            ans = Math.max(ans, w.time);

            for(int next : list[w.idx]) {

                if(--cnt[next]==0) {        //선행 일이 다 진행된 경우
                    pq.add(new Work(w.time+time[next], next));
                }
            }
        }
    }

    public static class Work implements Comparable<Work>{
        int time;
        int idx;

        public Work(int time, int idx) {
            this.time = time;
            this.idx = idx;
        }

        public int compareTo(Work w) {
            return this.time > w.time ? 1 : -1;
        }
    }
}