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

约 7 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为
标签
广度优先搜索 图

题目描述

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

image-20260928225926374

image-20260928225926375

题意分析

有向图中的边分为红色和蓝色，从节点 0 出发，求到每个节点的最短路径长度，要求相邻两条边的颜色不同。长度按边数计算，不可达节点返回 -1，起点自身的距离为 0。

图中可能存在自环或重复边。到达同一个节点时，如果最后一条边的颜色不同，下一步可以使用的边也不同，因此不能只用节点是否访问过来判断重复。

解法：带颜色状态的广度优先搜索

核心思路

[!blue]

将状态定义为 (node, lastColor)，表示刚沿颜色为 lastColor 的边到达 node。每个节点有两种状态：红边结束和蓝边结束。即使一个状态距离更短，它也无法代替另一状态，因为两者下一步允许的边颜色不同。

按颜色分别建立邻接表。扩展当前状态时，只扫描颜色 1 - lastColor 的出边，到达的状态记为 (next, nextColor)，这样所有生成的路径天然符合交替要求，不需要事后再次检查整条路线。

所有边长度为一，用 BFS 第一次到达某个完整状态时，就得到该状态的最短距离。dist[node][color] 初始为 -1，首次入队前写入距离，同时充当访问标记；自环可以改变末边颜色，但每个完整状态最多扩展一次，不会无限循环。

起点还没有经过任何边，第一步可以选红或蓝。因此把节点 0 的两种虚拟末边状态都以距离零入队，一种允许接蓝边，另一种允许接红边，不会限制第一步的颜色。

搜索结束后，目标路径可以用任意颜色结束，所以对每个节点取两种有效距离的较小值。只有一种可达就取那一种，两种都为 -1 才表示不可达。

解题步骤

  1. 为红边、蓝边分别建立有向邻接表。
  2. 将每个节点的两种距离设为 -1，再把起点两种状态都设为 0 并入队。
  3. 弹出状态后，只沿与末边相反颜色的出边扩展。
  4. 对尚未访问的 (next, nextColor)，记录当前距离加一并入队。
  5. BFS 结束后，逐节点合并红、蓝两种距离，忽略无效的 -1，返回结果数组。

代码实现

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        java.util.List<Integer>[][] graph = new java.util.ArrayList[2][n];

        for (int color = 0; color < 2; color++) {
            for (int i = 0; i < n; i++) {
                graph[color][i] = new java.util.ArrayList<>();
            }
        }

        for (int[] edge : redEdges) {
            graph[0][edge[0]].add(edge[1]);
        }

        for (int[] edge : blueEdges) {
            graph[1][edge[0]].add(edge[1]);
        }

        int[][] dist = new int[n][2];

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

        java.util.Queue<int[]> queue = new java.util.ArrayDeque<>();

        // 起点没有末边，两种虚拟状态分别允许第一步红或蓝。
        dist[0][0] = 0;
        dist[0][1] = 0;
        queue.offer(new int[] {
            0,
            0
        });
        queue.offer(new int[] {
            0,
            1
        });

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int node = state[0];
            int lastColor = state[1];
            // 只生成异色转移，交替约束直接写入邻接选择。
            int nextColor = 1 - lastColor;

            for (int next : graph[nextColor][node]) {
                if (dist[next][nextColor] != -1) {
                    continue;
                }

                // 第一次发现完整状态就记距离，避免重复入队。
                dist[next][nextColor] = dist[node][lastColor] + 1;
                queue.offer(new int[] {
                    next,
                    nextColor
                });
            }
        }

        int[] answer = new int[n];

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

        return answer;
    }
}

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
    graph := make([][][]int, 2)
    for color := 0; color < 2; color++ {
        graph[color] = make([][]int, n)
    }

    for _, edge := range redEdges {
        graph[0][edge[0]] = append(graph[0][edge[0]], edge[1])
    }
    for _, edge := range blueEdges {
        graph[1][edge[0]] = append(graph[1][edge[0]], edge[1])
    }

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

    queue := [][2]int{
        {0, 0},
        {0, 1},
    }
    // 起点没有末边，两种虚拟状态分别允许第一步红或蓝。
    dist[0][0] = 0
    dist[0][1] = 0

    for head := 0; head < len(queue); head++ {
        state := queue[head]
        node := state[0]
        lastColor := state[1]
        // 只生成异色转移，交替约束直接写入邻接选择。
        nextColor := 1 - lastColor

        for _, next := range graph[nextColor][node] {
            if dist[next][nextColor] != -1 {
                continue
            }
            // 第一次发现完整状态就记距离，避免重复入队。
            dist[next][nextColor] = dist[node][lastColor] + 1
            queue = append(queue, [2]int{
                next,
                nextColor,
            })
        }
    }

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

    return answer
}

复杂度分析

设节点数为 n，两种颜色的边总数为 E。

  • 时间复杂度：$O(n+E)$。共有 2n 个状态，每种状态最多入队一次，每条边只从能够选择它的异色前态扫描。
  • 空间复杂度：$O(n+E)$，邻接表保存边，距离数组和队列保存节点颜色状态。

关键点总结

[!green]

  • 把影响下一步选择的末边颜色纳入状态，才能正确区分到达同一节点的路线。
  • 交替条件体现在选择另一种颜色的邻接表，BFS 负责保证距离最短。
  • 起点两种虚拟状态允许任意首边颜色，终点两种状态则合并为一个最短答案。

易错点总结

[!yellow]

  • 只按节点去重，会拒绝较晚到达但末边颜色不同的状态，漏掉后续可行路径。
  • 起点只入队一种虚拟颜色，会无意限制第一条边的颜色。
  • 继续扫描当前颜色的出边，会生成连续同色路径，失去题目约束。
  • 首次发现后不立即记录距离，重复边和自环可能导致同一状态重复入队。
  • 直接对两种距离取最小值，会让代表不可达的 -1 覆盖真正的非负距离，必须先排除无效值。

相似题目

题目 难度 关联与区别
1293. 网格中的最短路径 困难 同样不能只按节点去重，原题状态还含剩余消障次数，本题还含上一条边的颜色。
847. 访问所有节点的最短路径 困难 同样把位置与额外历史状态组合后做BFS，本题只记最近颜色，原题记已访问集合。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/18525565
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！