Posted on 2023-10-18 21:57
Uriel 閱讀(30)
評論(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)