题目：

在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。

red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]
示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]
示例 3：

输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]
示例 4：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]
示例 5：

输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]

提示：

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

思路：

计算最短路径，可以使用广度优先搜索实现。

由于题目中的图的表示方式是边数组，为了方便处理，需要首先将边数组转换成邻接结点列表的形式，转换后可以在 O(1)O(1) 时间获得一个结点的全部相邻结点，然后使用广度优先搜索遍历图。

由于这道题要求不同颜色边的颜色交替，因此需要分别得到红边和蓝边的邻接结点列表，广度优先搜索的状态包括结点和上次访问的边的颜色，需要记录每个结点分别以两种颜色的边作为结尾的路径长度。

初始时，结点 00 对应的红边路径和蓝边路径的长度都是 00。对于每个状态，其后续状态的结点为从当前结点出发经过一条颜色不同的路径到达的结点，其后续状态的颜色为与当前状态不同的颜色。

遍历结束后，每个结点的最短路径长度为该结点的红边路径长度和蓝边路径长度中的最小值。如果一个结点使用两种颜色的路径都不能到达，则该结点的最短路径长度为 -1−1。

java代码：

class Solution {

    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Set<Integer>> reds = new ArrayList<>();
        List<Set<Integer>> blues = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            reds.add(new HashSet<>());
            blues.add(new HashSet<>());
        }
        for (int i = 0; i < redEdges.length; i++) {
            int[] r = redEdges[i];
            reds.get(r[0]).add(r[1]);
        }
        for (int i = 0; i < blueEdges.length; i++) {
            int[] r = blueEdges[i];
            blues.get(r[0]).add(r[1]);
        }
        int ans[] = new int[n];
        boolean redhere[] = new boolean[n];
        boolean bluehere[] = new boolean[n];
        Arrays.fill(ans, -1);
        ans[0] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { -1, 0, 0 });// 0red,1blue,step
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int from = cur[0], index = cur[1], step = cur[2] + 1;
            if (from == 0 || from == -1) {// 曾经以红色抵达index
                Set<Integer> set = blues.get(index);
                for (int b : set) {
                    if (!bluehere[b]) {
                        bluehere[b] = true;
                        if (ans[b] == -1) {
                            ans[b] = step;
                        }
                        queue.add(new int[] { 1, b, step });
                    }
                }
            }
            if (from == 1 || from == -1) {// 曾经以蓝色抵达index
                Set<Integer> set = reds.get(index);
                for (int b : set) {
                    if (!redhere[b]) {
                        redhere[b] = true;
                        if (ans[b] == -1) {
                            ans[b] = step;
                        }
                        queue.add(new int[] { 0, b, step });
                    }
                }
            }
        }
        return ans;
    }


}