题目如下：
Consider a directed graph, with nodes labelled
0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.Each
[i, j]inred_edgesdenotes a red directed edge from nodeito nodej. Similarly, each[i, j]inblue_edgesdenotes a blue directed edge from nodeito nodej.Return an array
answerof lengthn, where eachanswer[X]is the length of the shortest path from node0to nodeXsuch that the edge colors alternate along the path (or-1if such a path doesn‘t exist).
Example 1:
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = [] Output: [0,1,-1]Example 2:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]] Output: [0,1,-1]Example 3:
Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]] Output: [0,-1,-1]Example 4:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]] Output: [0,1,2]Example 5:
Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]] Output: [0,1,1]
Constraints:
1 <= n <= 100red_edges.length <= 400blue_edges.length <= 400red_edges[i].length == blue_edges[i].length == 20 <= red_edges[i][j], blue_edges[i][j] < n
解题思路：本题采用BFS的思想。对于每一个节点来说，分别求出其红边和蓝边作为入口的最小值。
代码如下：
class Solution(object): def shortestAlternatingPaths(self, n, red_edges, blue_edges): """ :type n: int :type red_edges: List[List[int]] :type blue_edges: List[List[int]] :rtype: List[int] """ res = [0] + [float(‘inf‘)] * (n - 1) queue = [] red_used = [0] * len(red_edges) blue_used = [0] * len(blue_edges) def process(target, edges, res, color,used_list,step_count): for inx,(i, j) in enumerate(edges): used = used_list[inx] if i == target and used == 0: res[j] = min(res[j],step_count + 1) queue.append((j, color,step_count + 1)) used_list[inx] = 1 #red process(0, red_edges, res, ‘R‘,red_used,0) while len(queue) > 0: num, color,step = queue.pop(0) if color == ‘R‘: process(num, blue_edges, res, ‘B‘,blue_used,step) else: process(num, red_edges, res, ‘R‘,red_used,step) red_used = [0] * len(red_edges) blue_used = [0] * len(blue_edges) process(0, blue_edges, res, ‘B‘, blue_used,0) while len(queue) > 0: num, color,step = queue.pop(0) if color == ‘R‘: process(num, blue_edges, res, ‘B‘,blue_used,step) else: process(num, red_edges, res, ‘R‘,red_used,step) res = map(lambda x: x if x != float(‘inf‘) else -1, res) return res
【leetcode】1129. Shortest Path with Alternating Colors
原文：https://www.cnblogs.com/seyjs/p/11302132.html