Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出n个节点的有向图边集,分为红色边和蓝色边,开始位于节点0,问依次经过红色蓝色边到达节点0~n-1的最短路径,若不可达,输出-1
为两个不同颜色的边集分别建立dict,color分别设为0和1,初始节点的color设为-1,从0开始BFS,走过的边把color值设为-1


 1 #1129
 2 #Runtime: 64 ms (Beats 75.93%)
 3 #Memory: 13.6 MB (Beats 90.74%)
 4 
 5 class Solution(object):
 6     def shortestAlternatingPaths(self, n, redEdges, blueEdges):
 7         """
 8         :type n: int
 9         :type redEdges: List[List[int]]
10         :type blueEdges: List[List[int]]
11         :rtype: List[int]
12         """
13         graph = defaultdict(list)
14         for x, y in redEdges:
15             graph[x].append((y, 0))
16         for x, y in blueEdges:
17             graph[x].append((y, 1))
18         q = deque([(0, -1)])
19         ans = [-1] * n
20         stp = 0
21         while q:
22             sz = len(q)
23             while sz > 0:
24                 sz -= 1
25                 x, fg = q.popleft()
26                 if ans[x] == -1:
27                     ans[x] = stp
28                 for i, (y, f) in enumerate(graph[x]):
29                     if y == -1 or f == fg:
30                         continue
31                     q.append((y, f))
32                     graph[x][i] = (-1, f)
33             stp += 1
34         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理