Parallel Courses III

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> adj(n);
        vector<int> indeg(n, 0);
        for (auto& r : relations) {
            adj[r[0] - 1].push_back(r[1] - 1);
            ++indeg[r[1] - 1];
        }
        queue<int> q;
        vector<int> done(n, 0);
        for (int i = 0; i < n; ++i) if (indeg[i] == 0) { q.push(i); done[i] = time[i]; }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                done[v] = max(done[v], done[u] + time[v]);
                if (--indeg[v] == 0) q.push(v);
            }
        }
        return *max_element(done.begin(), done.end());
    }
};

func minimumTime(n int, relations [][]int, time []int) int {
    adj := make([][]int, n)
    indeg := make([]int, n)
    for _, r := range relations {
        adj[r[0]-1] = append(adj[r[0]-1], r[1]-1)
        indeg[r[1]-1]++
    }
    q := []int{}
    done := make([]int, n)
    for i := 0; i < n; i++ {
        if indeg[i] == 0 {
            q = append(q, i)
            done[i] = time[i]
        }
    }
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        for _, v := range adj[u] {
            if done[u]+time[v] > done[v] {
                done[v] = done[u] + time[v]
            }
            indeg[v]--
            if indeg[v] == 0 {
                q = append(q, v)
            }
        }
    }
    best := 0
    for _, d := range done {
        if d > best {
            best = d
        }
    }
    return best
}

from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        adj = [[] for _ in range(n)]
        indeg = [0] * n
        for a, b in relations:
            adj[a - 1].append(b - 1)
            indeg[b - 1] += 1
        q = deque()
        done = [0] * n
        for i in range(n):
            if indeg[i] == 0:
                q.append(i)
                done[i] = time[i]
        while q:
            u = q.popleft()
            for v in adj[u]:
                if done[u] + time[v] > done[v]:
                    done[v] = done[u] + time[v]
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return max(done)

function minimumTime(n, relations, time) {
    const adj = Array.from({ length: n }, () => []);
    const indeg = new Array(n).fill(0);
    for (const [a, b] of relations) {
        adj[a - 1].push(b - 1);
        indeg[b - 1]++;
    }
    const q = [];
    const done = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        if (indeg[i] === 0) {
            q.push(i);
            done[i] = time[i];
        }
    }
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        for (const v of adj[u]) {
            if (done[u] + time[v] > done[v]) {
                done[v] = done[u] + time[v];
            }
            if (--indeg[v] === 0) q.push(v);
        }
    }
    let best = 0;
    for (const d of done) if (d > best) best = d;
    return best;
}

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] r : relations) {
            adj.get(r[0] - 1).add(r[1] - 1);
            indeg[r[1] - 1]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        int[] done = new int[n];
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                q.offer(i);
                done[i] = time[i];
            }
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (done[u] + time[v] > done[v]) {
                    done[v] = done[u] + time[v];
                }
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        int best = 0;
        for (int d : done) if (d > best) best = d;
        return best;
    }
}

function minimumTime(n: number, relations: number[][], time: number[]): number {
    const adj: number[][] = Array.from({ length: n }, () => []);
    const indeg: number[] = new Array(n).fill(0);
    for (const [a, b] of relations) {
        adj[a - 1].push(b - 1);
        indeg[b - 1]++;
    }
    const q: number[] = [];
    const done: number[] = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        if (indeg[i] === 0) {
            q.push(i);
            done[i] = time[i];
        }
    }
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        for (const v of adj[u]) {
            if (done[u] + time[v] > done[v]) {
                done[v] = done[u] + time[v];
            }
            if (--indeg[v] === 0) q.push(v);
        }
    }
    let best = 0;
    for (const d of done) if (d > best) best = d;
    return best;
}