本文共 3426 字，大约阅读时间需要 11 分钟。

1129. 颜色交替的最短路径（JAVA代码解题）

在一个有向图中，节点分别标记为 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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shortest-path-with-alternating-colors 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

算法实现

package com.bean.leetcode;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedList;import java.util.Map;import java.util.Queue;import java.util.Set;public class Solution1129 {		private int[] ans;	public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {		ans = new int[n];		for (int i = 1; i < n; i++) {			ans[i] = Integer.MAX_VALUE;		}		Map
   
    > redMap = new HashMap<>(16);		Map
    
     > blueMap = new HashMap<>(16);		for (int[] redEdge : redEdges) {			redMap.putIfAbsent(redEdge[0], new HashSet<>());			redMap.get(redEdge[0]).add(redEdge[1]);		}		for (int[] blueEdge : blueEdges) {			blueMap.putIfAbsent(blueEdge[0], new HashSet<>());			blueMap.get(blueEdge[0]).add(blueEdge[1]);		}		// 红边为起点		int len = 0;		boolean isRed = true;		boolean[] visitedRed = new boolean[n];		boolean[] visitedBlue = new boolean[n];		visitedRed[0] = true;		Queue
     
       queue = new LinkedList<>();		for (int[] edge : redEdges) {			if (edge[0] == 0) {				queue.offer(edge[1]);			}		}		bfs(redMap, blueMap, len, isRed, visitedRed, visitedBlue, queue);		// 蓝边为起点		isRed = false;		visitedRed = new boolean[n];		visitedBlue = new boolean[n];		len = 0;		queue.clear();		for (int[] edge : blueEdges) {			if (edge[0] == 0) {				queue.offer(edge[1]);			}		}		bfs(redMap, blueMap, len, isRed, visitedRed, visitedBlue, queue);		for (int i = 0; i < ans.length; i++) {			if (ans[i] == Integer.MAX_VALUE) {				ans[i] = -1;			}		}		return ans;	}    private void bfs(Map
      
       > redMap,                     Map
       
        > blueMap,                     int len, boolean isRed,                     boolean[] visitedRed, boolean[] visitedBlue,                     Queue
        
         queue) { while (!queue.isEmpty()) { int size = queue.size(); len++; if (isRed) { // queue中节点为红边终点，即下一步应该走蓝边 isRed = false; while (size-- > 0) { int idx = queue.remove(); if (!visitedBlue[idx]) { visitedBlue[idx] = true; ans[idx] = Math.min(ans[idx], len); Set
         
           desSet = blueMap.get(idx); if (desSet == null) { continue; } for (int d : desSet) { // 检查是否已经遍历过红边以d作为起点 if (!visitedRed[d]) { queue.offer(d); } } } } } else { // queue中节点为蓝边终点，即下一步应该走红边 isRed = true; while (size-- > 0) { int idx = queue.remove(); if (!visitedRed[idx]) { visitedRed[idx] = true; ans[idx] = Math.min(ans[idx], len); Set
          
            desSet = redMap.get(idx); if (desSet == null) { continue; } for (int d : desSet) { // 检查是否已经遍历过蓝边以d作为起点 if (!visitedBlue[d]) { queue.offer(d); } } } } } } }}
          
         
        
       
      
     
    
   

提交后Accepted~