LeetCode 1129. 颜色交替的最短路径

Categories:

题目描述
思路分析
1. 解法一：分色 BFS（推荐）
相似题目

题目描述

✅ 1129. 颜色交替的最短路径

思路分析

解法一：分色 BFS（推荐）

核心思路：

对每个节点分别记录以红边或蓝边结尾的最短距离。

BFS 队列中携带当前节点与边颜色，下一步只能走相反颜色。

取两种颜色距离的最小值作为答案。

复杂度分析：

时间复杂度：O(n + m)，其中 n 表示节点数，m 表示边数。

空间复杂度：O(n + m)，用于图与队列。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[] red = new List[n];
        List<Integer>[] blue = new List[n];
        for (int i = 0; i < n; i++) {
            red[i] = new ArrayList<>();
            blue[i] = new ArrayList<>();
        }
        for (int[] e : redEdges) {
            red[e[0]].add(e[1]);
        }
        for (int[] e : blueEdges) {
            blue[e[0]].add(e[1]);
        }

        int[][] dist = new int[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], -1);
        }

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});
        queue.offer(new int[]{0, 1});
        dist[0][0] = 0;
        dist[0][1] = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int node = cur[0];
            int color = cur[1];

            List<Integer>[] nextGraph = (color == 0) ? blue : red;
            for (int next : nextGraph[node]) {
                if (dist[next][1 - color] == -1) {
                    dist[next][1 - color] = dist[node][color] + 1;
                    queue.offer(new int[]{next, 1 - color});
                }
            }
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            if (dist[i][0] == -1) {
                res[i] = dist[i][1];
            } else if (dist[i][1] == -1) {
                res[i] = dist[i][0];
            } else {
                res[i] = Math.min(dist[i][0], dist[i][1]);
            }
        }

        return res;
    }
}

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
	red := make([][]int, n)
	blue := make([][]int, n)
	for _, e := range redEdges {
		red[e[0]] = append(red[e[0]], e[1])
	}
	for _, e := range blueEdges {
		blue[e[0]] = append(blue[e[0]], e[1])
	}

	dist := make([][2]int, n)
	for i := 0; i < n; i++ {
		dist[i][0] = -1
		dist[i][1] = -1
	}

	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0}, [2]int{0, 1})
	dist[0][0] = 0
	dist[0][1] = 0

	for head := 0; head < len(queue); head++ {
		cur := queue[head]
		node, color := cur[0], cur[1]

		var nextGraph [][]int
		if color == 0 {
			nextGraph = blue
		} else {
			nextGraph = red
		}

		for _, next := range nextGraph[node] {
			if dist[next][1-color] == -1 {
				dist[next][1-color] = dist[node][color] + 1
				queue = append(queue, [2]int{next, 1 - color})
			}
		}
	}

	res := make([]int, n)
	for i := 0; i < n; i++ {
		if dist[i][0] == -1 {
			res[i] = dist[i][1]
		} else if dist[i][1] == -1 {
			res[i] = dist[i][0]
		} else if dist[i][0] < dist[i][1] {
			res[i] = dist[i][0]
		} else {
			res[i] = dist[i][1]
		}
	}

	return res
}

相似题目

题目	难度	考察点
1091. 二进制矩阵中的最短路径	中等	BFS
127. 单词接龙	困难	BFS
752. 打开转盘锁	中等	BFS
847. 访问所有节点的最短路径	困难	BFS
787. K 站中转内最便宜的航班	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/18525565