給出n個節(jié)點的有向圖邊集，分為紅色邊和藍色邊，開始位于節(jié)點0，問依次經(jīng)過紅色藍色邊到達節(jié)點0～n-1的最短路徑，若不可達，輸出-1
為兩個不同顏色的邊集分別建立dict，color分別設(shè)為0和1，初始節(jié)點的color設(shè)為-1，從0開始BFS，走過的邊把color值設(shè)為-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