```python
from collections import deque
from typing import List

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        # 构建图 (0-index)
        graph = [[] for _ in range(n)]
        indegree = [0] * n
        for u, v in relations:
            u -= 1
            v -= 1
            graph[u].append(v)
            indegree[v] += 1

        # dp[i] 表示完成课程 i 的最早时间
        dp = [0] * n
        q = deque()

        # 初始化入度为 0 的课程
        for i in range(n):
            if indegree[i] == 0:
                dp[i] = time[i]
                q.append(i)

        # 拓扑排序 + DP
        while q:
            u = q.popleft()
            for v in graph[u]:
                # 更新后继课程的最早完成时间
                dp[v] = max(dp[v], dp[u] + time[v])
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)

        # 所有课程完成时间的最大值即为答案
        return max(dp)
```

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐