给出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