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