1129. Shortest Path with Alternating Colors =========================================== 题目信息 -------- :题号: 1129 :难度: Medium :主题: 有向图、广度优先搜索、颜色交替 :原题: `LeetCode 1129 `_ :重点: 相邻边颜色必须交替,第一条边可为任意颜色;图允许自环和平行边,不可达节点返回 ``-1`` 题目重述 -------- 给定含 ``n`` 个节点的有向图,节点编号为 ``0`` 到 ``n - 1``。``redEdges`` 和 ``blueEdges`` 分别给出红色与蓝色有向边,图中可以存在自环或相同端点的平行边。 对于每个节点 ``x``,寻找从节点 ``0`` 到 ``x`` 的最短路径,要求路径中相邻边颜色不同。第一条边颜色不限。请返回长度为 ``n`` 的数组;起点距离为 ``0``,不存在合法路径的节点距离为 ``-1``。 ``1 <= n <= 100``,两种边的数量均不超过 ``400``,每条边的两个端点都在 ``[0,n-1]`` 范围内。 自建示例 -------- 三条边严格交替到达末端: .. code-block:: text 输入:n = 4, redEdges = [[0,1],[2,3]], blueEdges = [[1,2]] 输出:[0,1,2,3] 解释:路径 0 -> 1 -> 2 -> 3 的颜色依次为红、蓝、红,满足交替要求。 图中只有起点: .. code-block:: text 输入:n = 1, redEdges = [], blueEdges = [] 输出:[0] 解释:从起点到自身不需要经过任何边,最短距离为 0。