Posted on 2023-10-18 21:57
Uriel 阅读(7)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
闲来无事重切Leet Code
有一系列课程，每个课程有一些先修课，修每门课需要时间time[i]，问最少多长时间能修完所有课，拓扑排序
1 #2050
2
3 #Runtime: 1240 ms (Beats 72.73%)
4 #Memory: 43.6 MB (Beats 31.82%)
5
6 class Solution(object):
7 def minimumTime(self, n, relations, time):
8 """
9 :type n: int
10 :type relations: List[List[int]]
11 :type time: List[int]
12 :rtype: int
13 """
14 adj = defaultdict(list)
15 ind = [0] * n
16 time_cost = [0] * n
17 for x, y in relations:
18 adj[x - 1].append(y - 1)
19 ind[y - 1] += 1
20 q = deque([])
21 for x in range(n):
22 if ind[x] == 0:
23 q.append(x)
24 time_cost[x] = time[x]
25 while len(q):
26 x = q.popleft()
27 for y in adj[x]:
28 time_cost[y] = max(time_cost[x] + time[y], time_cost[y])
29 ind[y] -= 1
30 if ind[y] == 0:
31 q.append(y)
32 return max(time_cost)