颜色交替的最短路径 图解题解

这道题到底在问什么

输入

n=3, redEdges=[[0,1],[1,2]], blueEdges=[]

输出

[0,1,-1]（0→1 红可达 1 步;再走 1→2 又是红,不交替,所以 2 号不可达）

输入

本节 n=5, redEdges=[[0,1],[1,2],[2,3]], blueEdges=[[0,2],[2,4]]

输出

[0,1,1,2,-1]

最优解：一步一步想明白

1. 3记牢一句话:状态带上颜色,每走一步翻一次色,第一次够到一个点的层数就是它的最短交替路径长度。
2. 4目标:从 0 出发,每步颜色都和上一步不同,求到每个点的最短步数先把图看懂。五个圆圈是节点 0 到 4,箭头是有向边,每条边旁边标了颜色:红或蓝。题目要的是从节点 0 出发,走一条红蓝交替的路,也就是这一步红、下一步必须蓝,再下一步又得红,这样交替着走,问到每个点最少要几步。走不到的记成 -1。先把答案亮出来,最后会是 0、1、1、2、-1,其中 4 号谁也送不到。下面一步步把它跑出来。
3. 5把 (0,红到) 和 (0,蓝到) 都放进队列,层数 d=0这里有个关键设计:我们记的状态不是单纯「在哪个点」,而是「在哪个点,上一步走的是什么颜色」,因为下一步颜色由它决定。0 号是起点还没走过边,为了红蓝两种开局都能展开,就放两个起点状态进队列:一个当作刚用红边到的 0 号,下一步就该走蓝;一个当作刚用蓝边到的 0 号,下一步走红。当前层数 d 记为 0。注意一个细节:这两个起点状态放进队列的同一刻,就一并记进了已访问,所以右边已访问那栏现在已经列着「0号·红」「0号·蓝」两条;入队就标记,是为了同一个状态绝不会被重复入队。
4. 6第一次到 0 号,answer[0] = 0从队头取出状态「0号·红到」,它是这一层 d=0 的。0 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 0,这就是最短交替路径长度,记 answer[0] = 0。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
5. 7下一步必须翻到 蓝 色「0号·红到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 0 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 红 边,按交替规矩,下一步只能走 蓝 边,于是去看从 0 号出发的 蓝 色边有哪些。
6. 8(2号,蓝) 入队并同步记进已访问,等下一层从 0 号顺着这条 蓝 色边走到 2 号。状态「2号·蓝到」之前没访问过,就在放进队列的同一刻把它记进已访问,右边已访问那栏立刻多出这一条,排到队尾等下一层 d=1 再处理。入队就标记,哪怕图里有平行边,同一个状态也只会入队一次。2 号先点亮成待探索。继续看 0 号还有没有别的 蓝 边。
7. 90 号早有答案 0,不再更新取出「0号·蓝到」。0 号在更早的层里已经拿到过答案 0 了,后到的只会更长,所以这里不更新它的答案,只把这个状态当作继续往外扩的跳板。
8. 10下一步必须翻到 红 色「0号·蓝到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 0 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 蓝 边,按交替规矩,下一步只能走 红 边,于是去看从 0 号出发的 红 色边有哪些。
9. 11(1号,红) 入队并同步记进已访问,等下一层从 0 号顺着这条 红 色边走到 1 号。状态「1号·红到」之前没访问过,就在放进队列的同一刻把它记进已访问,右边已访问那栏立刻多出这一条,排到队尾等下一层 d=1 再处理。入队就标记,哪怕图里有平行边,同一个状态也只会入队一次。1 号先点亮成待探索。继续看 0 号还有没有别的 红 边。
10. 12第一次到 2 号,answer[2] = 1从队头取出状态「2号·蓝到」,它是这一层 d=1 的。2 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 1,这就是最短交替路径长度,记 answer[2] = 1。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
11. 13下一步必须翻到 红 色「2号·蓝到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 2 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 蓝 边,按交替规矩,下一步只能走 红 边,于是去看从 2 号出发的 红 色边有哪些。
12. 14(3号,红) 入队并同步记进已访问,等下一层从 2 号顺着这条 红 色边走到 3 号。状态「3号·红到」之前没访问过,就在放进队列的同一刻把它记进已访问,右边已访问那栏立刻多出这一条,排到队尾等下一层 d=2 再处理。入队就标记,哪怕图里有平行边,同一个状态也只会入队一次。3 号先点亮成待探索。继续看 2 号还有没有别的 红 边。
13. 15第一次到 1 号,answer[1] = 1从队头取出状态「1号·红到」,它是这一层 d=1 的。1 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 1,这就是最短交替路径长度,记 answer[1] = 1。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
14. 16下一步必须翻到 蓝 色「1号·红到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 1 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 红 边,按交替规矩,下一步只能走 蓝 边,于是去看从 1 号出发的 蓝 色边有哪些。
15. 17这一支走到头了从 1 号出发,蓝 色的边一条也没有。交替的链子在这里断了,这个状态没法再往外送任何新点,1 号这一支到此为止。回到队列继续处理别的状态。
16. 18第一次到 3 号,answer[3] = 2从队头取出状态「3号·红到」,它是这一层 d=2 的。3 号此前还没被任何路径碰到过,所以第一次到它的步数就是当前层数 2,这就是最短交替路径长度,记 answer[3] = 2。BFS 一层层往外扩,头一次够到一个点,那一定是最短的。
17. 19下一步必须翻到 蓝 色「3号·红到」这个状态早在入队那一刻就记进了已访问,右边一直列着它,标的是节点和颜色这一对,不是光记 3 号。这一点后面会变成胜负手。现在把它出队展开:刚走的是 红 边,按交替规矩,下一步只能走 蓝 边,于是去看从 3 号出发的 蓝 色边有哪些。
18. 20这一支走到头了从 3 号出发,蓝 色的边一条也没有。交替的链子在这里断了,这个状态没法再往外送任何新点,3 号这一支到此为止。回到队列继续处理别的状态。
19. 21到 4 号要走蓝边 2→4,而那需要「红色到 2」队列空了,可 4 号始终没拿到答案。看清原因:唯一能进 4 号的是蓝边 2→4,要走这条蓝边,就得先「用红边到达 2 号」,这样下一步才轮到蓝。可整趟里,2 号只被「蓝色到」过,从没被「红色到」过。所以红色到 2 这个状态压根没出现,蓝边 2→4 永远迈不出去。
20. 224 号 -1 来自到达颜色;两层记账兜的是要重进队的图顺带说清 visited 为什么按节点加颜色两层记,先纠一个误读:4 号是 -1,根子在状态自带的到达颜色。正因为状态带着颜色,我们才确认 2 号只蓝到、没红到,蓝边 2→4 的前一步红色到 2 没出现,4 号才到不了,这跟去重怎么记无关。两层记账真正的用武之地是另一张图:某个点既被红色到、又得以蓝色到的身份再进一次队,才能够到后面的点;只按节点去重就会把这第二次当重复挡掉,把那些点冤枉成不可达。本节没触发这种重进队的情形,但记法照两层来,换张图就靠它兜底。
21. 23答案 answer = [0,1,1,2,-1]全部跑完,答案凑齐:0 号 0 步,1 号和 2 号各 1 步,3 号 2 步,4 号到不了记 -1。回放一下 3 号怎么来的:0 号先走蓝边到 2 号(第 1 步),再从 2 号走红边到 3 号(第 2 步),红蓝交替成立,正好 2 步。整道题一句话:状态带上颜色做 BFS,每步翻色,第一次够到就是最短。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def shortestAlternatingPaths(
        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]
    ) -> List[int]:
        g = [defaultdict(list), defaultdict(list)]
        for i, j in redEdges:
            g[0][i].append(j)
        for i, j in blueEdges:
            g[1][i].append(j)
        ans = [-1] * n
        vis = {(0, 0), (0, 1)}            # 起点两个状态先标记已访问
        q = deque([(0, 0), (0, 1)])
        d = 0
        while q:
            for _ in range(len(q)):
                i, c = q.popleft()
                if ans[i] == -1:
                    ans[i] = d
                c ^= 1
                for j in g[c][i]:
                    if (j, c) not in vis:
                        vis.add((j, c))      # 先标记
                        q.append((j, c))     # 再入队:同一状态只入队一次
            d += 1
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<vector<int>>> g(2, vector<vector<int>>(n));
        for (auto& e : redEdges) {
            g[0][e[0]].push_back(e[1]);
        }
        for (auto& e : blueEdges) {
            g[1][e[0]].push_back(e[1]);
        }
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        q.emplace(0, 1);
        bool vis[n][2];
        memset(vis, false, sizeof vis);
        vis[0][0] = vis[0][1] = true;       // 起点两个状态先标记已访问
        vector<int> ans(n, -1);
        int d = 0;
        while (!q.empty()) {
            for (int k = q.size(); k; --k) {
                auto [i, c] = q.front();
                q.pop();
                if (ans[i] == -1) {
                    ans[i] = d;
                }
                c ^= 1;
                for (int& j : g[c][i]) {
                    if (!vis[j][c]) {
                        vis[j][c] = true;   // 先标记
                        q.emplace(j, c);    // 再入队:同一状态只入队一次
                    }
                }
            }
            ++d;
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[][] g = new List[2][n];
        for (List<Integer>[] f : g) {
            Arrays.setAll(f, k -> new ArrayList<>());
        }
        for (int[] e : redEdges) {
            g[0][e[0]].add(e[1]);
        }
        for (int[] e : blueEdges) {
            g[1][e[0]].add(e[1]);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {0, 0});
        q.offer(new int[] {0, 1});
        boolean[][] vis = new boolean[n][2];
        vis[0][0] = vis[0][1] = true;       // 起点两个状态先标记已访问
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        int d = 0;
        while (!q.isEmpty()) {
            for (int k = q.size(); k > 0; --k) {
                int[] p = q.poll();
                int i = p[0], c = p[1];
                if (ans[i] == -1) {
                    ans[i] = d;
                }
                c ^= 1;
                for (int j : g[c][i]) {
                    if (!vis[j][c]) {
                        vis[j][c] = true;       // 先标记
                        q.offer(new int[] {j, c}); // 再入队:同一状态只入队一次
                    }
                }
            }
            ++d;
        }
        return ans;
    }
}

复杂度

面试官可能追问