Independent prerequisite branches run concurrently. Only the slowest required chain delays the next course. Summing would count work that happens at the same time.

finish[v] is the earliest achievable completion time of v, including v’s own duration. Initialize it to that duration. For each processed edge u→v, offer finish[u]+duration[v]. Keep the maximum offer because every prerequisite must finish. Kahn’s incoming count releases v only after all offers arrive. By induction in topological order, each finalized finish value is both necessary and achievable with unlimited parallelism. The overall answer is the largest course finish.

What the function promises: n courses are labeled 1..n. Each relation [u,v] means finish u before v. durations is indexed from zero. Durations are nonnegative and workers are unlimited. Return minimum completion time, or None for an invalid cyclic prerequisite system.

from collections import deque

def minimum_course_time(n, relations, durations):
    graph = [[] for _ in range(n)]
    incoming = [0] * n
    for earlier, later in relations:
        u, v = earlier - 1, later - 1
        graph[u].append(v)
        incoming[v] += 1
    finish = list(durations)
    ready = deque(i for i in range(n) if incoming[i] == 0)
    processed = 0
    while ready:
        u = ready.popleft()
        processed += 1
        for v in graph[u]:
            finish[v] = max(finish[v], finish[u] + durations[v])
            incoming[v] -= 1
            if incoming[v] == 0:
                ready.append(v)
    return max(finish, default=0) if processed == n else None

assert minimum_course_time(3, [(1,3), (2,3)], [2,5,3]) == 8
assert minimum_course_time(2, [(1,2), (2,1)], [1,1]) is None
assert minimum_course_time(0, [], []) == 0

Work and storage: O(V+E) time and space, with no recursion. “Longest path” is tractable here because the dependency graph is acyclic, not because longest paths are easy on arbitrary graphs.

When to recognize it: A course waits for its slowest prerequisite chain, not the sum of independent chains.

Check before applying it: A topological order alone is not a duration. Limited workers would create a different scheduling problem.

Keep the topological order. Set ways[source]=1 and other counts to zero, then add ways[u] into ways[v] for each edge u→v. Use addition rather than maximum because distinct incoming paths are all counted. State meaning determines the combine operation.